1. Standard memberDeepThought
    Losing the Thread
    Quarantined World
    Joined
    27 Oct '04
    Moves
    87415
    16 Jan '21 17:27
    What is the smallest prime number p such that:

    p³ + a² = b⁴

    where a and b are natural numbers (i.e. positive integers)?

    Just in case the Unicode didn't register properly on your machine that is:

    p^3 + a^2 = b^4.
  2. Standard memberBigDogg
    Secret RHP coder
    on the payroll
    Joined
    26 Nov '04
    Moves
    155080
    18 Jan '21 04:22
    Best I can do so far:

    Reveal Hidden Content
    p = 23; b = 78; a = 6083
  3. Standard memberBigDogg
    Secret RHP coder
    on the payroll
    Joined
    26 Nov '04
    Moves
    155080
    18 Jan '21 05:422 edits
    Confirmed I've got the optimal answer.

    I solved it using programming over math.

    Edit: program process was:

    1) Make a list of prime numbers from 1 to 100
    2) Make a list of the cubes of those numbers
    3) Make lists of quads and squares
    4) For every cube on the list, go through the quads.
    5) Find the lowest quad greater than the cube.
    6) Look up that quad in the squares list.
    7) Subtract the next lower square from that quad, then the next lower, etc., until the difference is greater or equal to the cube.
    8) If equal, print the solution.
    9) If, on step 7, the very next lower square was already too greatly different, stop looking through the quads list, and go to the next cube on the cubes list. [This is mostly not to waste computing time.]
  4. Joined
    11 Nov '14
    Moves
    34223
    18 Jan '21 13:511 edit
    @BigDoggProblem

    Good work - I hoped there might be a solution not involving computer search.

    Got as far as a + 1 = b^2, and p^3 = 2b^2 - 1, but didn't see any way forward after that
  5. Joined
    18 Jan '07
    Moves
    12361
    18 Jan '21 17:18
    @blood-on-the-tracks said
    @BigDoggProblem

    Good work - I hoped there might be a solution not involving computer search.

    Got as far as a + 1 = b^2, and p^3 = 2b^2 - 1, but didn't see any way forward after that
    I'm sure this could've been done by hand, tediously, but with those numbers I don't think there's a reasonable way to do it with a logical argument. An exhaustive search is the only real solution.

    (And, unlike some, I don't believe a computer solution to an exhaustive search is inferior to a manual one if it's this drudge-workey. Tic tac toe or the Soma cube? Yeah, do it by hand. But meaningless number crunching is what computers are for in the first place.)
  6. R
    Standard memberRemoved
    Joined
    10 Dec '06
    Moves
    8528
    18 Jan '21 17:561 edit
    @blood-on-the-tracks said
    @BigDoggProblem

    Good work - I hoped there might be a solution not involving computer search.

    Got as far as a + 1 = b^2, and p^3 = 2b^2 - 1, but didn't see any way forward after that
    I suspect Deepthought is looking for an analytical solution...but I could be wrong.

    I don't know how you got to:

    b^2 = a+1

    But is there anything that can be further got from this:

    p^3 = b^4 - a^2

    p^3 = ( b^2 + a ) ( b^2 - a )

    Sub b^2 = a+1

    p^3 = ( 2a + 1)

    Then we see:

    a = ( p^3 - 1 ) / 2

    Then maybe difference of cubes factorization for the numerator:

    p^3 - 1 = ( p -1 ) ( p^2 - p + 1 )

    factor ( p - 1) must be even

    factor ( p^2 - p +1 ) must be odd = ( p ( p-1) + 1 )

    I don't know?... I'm pretty weak in number theory.
  7. Joined
    11 Nov '14
    Moves
    34223
    18 Jan '21 18:402 edits
    @joe-shmo

    Hi Joe

    It's the 'not knowing' if it's a 'pen, paper and calculator solution' or not, that made me stop.

    From your 'difference of 2 squares' on the RHS, that has to equal p x p x p. P itself is prime, so we can't 'mingle' the 3 p's. So the only way it can work is if the larger of the 2 bracketed numbers ( the one with the plus) equals p^2, and the other p, or the larger one is p^3 itself, and the other =1.

    I did a little work on the former(it leads into triangular numbers and all sorts of tangles), and dismissed that, so went with the latter.

    Thus, (b^2 - a) = 1, so b^2 = a + 1

    I looked at what you tried underneath, but I think I want another equation so I have 3 eqns and 3 unknowns.
  8. Standard memberBigDogg
    Secret RHP coder
    on the payroll
    Joined
    26 Nov '04
    Moves
    155080
    18 Jan '21 21:12
    @joe-shmo
    I suspect you're right. I did the programming solution because I enjoy that more.

    I'm interested to see if there is a logical solution also.
  9. Standard memberDeepThought
    Losing the Thread
    Quarantined World
    Joined
    27 Oct '04
    Moves
    87415
    19 Jan '21 14:38
    @bigdoggproblem said
    Best I can do so far:

    [hidden]p = 23; b = 78; a = 6083[/hidden]
    That is the correct answer. I'm wondering if it is possible to find an analytic solution. It's possible to eliminate the quadratic factorization analytically, we have:

    p³ = (b² + a) (b² - a)

    So either p² = (b² + a) and p = (b² - a), or p³ = (b² + a) and b² = a + 1. We can eliminate the former case as follows. Adding the expressions for p² and p we have:

    p² + p = 2b²

    if p = 2 then we have b = sqrt(3), which is not an integer so p must be an odd prime.

    Rearranging slightly we have:

    p [(p + 1)/2] = b²

    Since p > (p + 1)/2 the left hand side has a lone prime factor of p, but the right hand side is a quadratic and so the factors in its prime factorization must appear an even number of times, so by the fundamental theorem of arithmetic the expression cannot be true.

    This leaves the case p³ = (b² + a) and b² = a + 1,

    so:

    p³ = 2b² - 1,

    Brute force on a spreadsheet gave the same result as bigdoggproblem found above. The advantage with this is that a by hand solution becomes feasible if somewhat tedious.

    On my spreadsheet:

    The first column is b, numbering from 1 upwards.
    The second column finds 2b² - 1 using the first column as an input.
    The third column finds exp(ln(2b² - 1)/3)
    The forth is the third column + 1, as a rounding error check.
    The fifth and sixth columns round down to the nearest integer.
    The seventh column looks to see if the third column equals either the fifth or the sixth columns and prints yes if it does.

    I was told about this problem by a relative and so I don't know if the original setter was expecting an analytic solution. I wonder if it's possible to make analytical progress, beyond the above.
  10. Standard memberDeepThought
    Losing the Thread
    Quarantined World
    Joined
    27 Oct '04
    Moves
    87415
    19 Jan '21 15:15
    @joe-shmo said
    I suspect Deepthought is looking for an analytical solution...but I could be wrong.

    I don't know how you got to:

    b^2 = a+1

    But is there anything that can be further got from this:

    p^3 = b^4 - a^2

    p^3 = ( b^2 + a ) ( b^2 - a )

    Sub b^2 = a+1

    p^3 = ( 2a + 1)

    Then we see:

    a = ( p^3 - 1 ) / 2

    Then maybe difference of cubes factorization for the n ...[text shortened]... ( p^2 - p +1 ) must be odd = ( p ( p-1) + 1 )

    I don't know?... I'm pretty weak in number theory.
    Hi Joe,
    bigdoggproblem's brute force numerical solution is fine - he got the answer right and I didn't specify that the problem had to be solved analytically - in part because I don't know if it's possible or particularly easy. I was expecting solvers to find that the factorisation:

    p³ = b² + a, b² = a + 1

    I suspect that there's more than one way of showing that p² = b² + a and p = b² - a cannot be satisfied for p prime and a and b integer.

    I was interested to see if it's possible to make further progress analytically. I automatically looked at 2b² - 1 rather than 2a + 1. Which got me to p³ + 1 = 2b², which doesn't factorize neatly, but I'm looking at your expression. There's a sign error:

    p³ - 1 = (p - 1)(p² + p + 1) = 2(b² - 1) = 2(b + 1)(b - 1)

    I can't see how to make any progress with this. For the actual answer we have that p - 1 = 22, b - 1 = 77, so 2 (b-1) = 2*11*7 and p² + p + 1 = 7*(b + 1), since b + 1 = 78, we have b + 1 = 79 is prime. Maybe it's possible to do something with this factorization.
Back to Top

Cookies help us deliver our Services. By using our Services or clicking I agree, you agree to our use of cookies. Learn More.I Agree