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.]
- Joined
- 11 Nov 14
- Moves
- 34223
@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
- Joined
- 18 Jan 07
- Moves
- 12466
@blood-on-the-tracks saidI'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.
@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
(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.)
- Joined
- 10 Dec 06
- Moves
- 8528
@blood-on-the-tracks saidI suspect Deepthought is looking for an analytical solution...but I could be wrong.
@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 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.
- Joined
- 11 Nov 14
- Moves
- 34223
@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.
@bigdoggproblem saidThat 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:
Best I can do so far:
[hidden]p = 23; b = 78; a = 6083[/hidden]
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.
@joe-shmo saidHi Joe,
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.
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.