Problems & Puzzles: Puzzles

Puzzle 104. Numbers that are equal to the sum of cubes of its third parts (as strings)

Example:

333667001 = 333³ + 667³ +001³

Here are the first 23 of these numbers below 10^10 (*)

153, 370, 371, 407, 165033, 221859, 336700, 336701, 340067, 341067, 407000, 407001, 444664, 487215, 982827, 983221, 166500333, 296584415, 333667000, 333667001, 334000667, 710656413, 828538472, …

BTW, 333667001 is the only (& then the least) prime of this kind of numbers below 10^10.

Questions:

1. I have some empirical evidence that this sequence is infinite. Can you give a formal proof of it?
2. Find the following two primes in the sequence.

Generalizing the concept you may construct the following sequences:

a) Numbers that are equal to the sum of the squares of its halves.
b) Numbers that are equal to the sum of the four power of its fourth parts.
c) etc.

3. Obtain the corresponding sequences and remark the primes within.

Solution

"In the hope of finding prime solutions I started programming sub question 2a (numbers equal to the sum of the squares of its halves). The reason is because I remembered Harvey Heinz had some of these numbers published (not an exhaustive list btw) on his page about Narcissistic numbers : see www.geocities.com/CapeCanaveral/Launchpad/4057/ 

Here is the full list I got from my programming efforts. Curiously enough these solutions seems to come in pairs so now are 'two halves', 'squares' and 'pairs' involved :-) [bolds are mine, CR^]

---------------------------------------------------

L = 2 (nihil)

---------------------------------------------------

L = 4 (1 pair)

12_33 = 12^2 + 33^2 (°)
88_33 = 88^2 + 33^2 (°)

Note that the sum of the 'left halves' of each pair always add up to the nearest multiple of 10, in the above case 12 + 88 = 100. The 'right halves' are always identical.

---------------------------------------------------

L = 6 (1 pair)

010_100 = 010^2 + 100^2
990_100 = 990^2 + 100^2 (°)

---------------------------------------------------

L = 8 (1 pair)

0588_2353 = 0588^2 + 2353^2 *** PRIME ***
9412_2353 = 9412^2 + 2353^2 (°)

Note that 5882353 is PRIME !

---------------------------------------------------

L = 10 (3 pairs)

00990_09901 = 00990^2 + 09901^2
99010_09901 = 99010^2 + 09901^2
17650_38125 = 17650^2 + 38125^2 (°)
82350_38125 = 82350^2 + 38125^2 (°)
25840_43776 = 25840^2 + 43776^2 (°)
74160_43776 = 74160^2 + 43776^2 (°)

---------------------------------------------------

L = 12 (3 pairs)

000100_010000 = 000100^2 + 010000^2
999900_010000 = 999900^2 + 010000^2
116788_321168 = 116788^2 + 321168^2 (°)
883212_321168 = 883212^2 + 321168^2 (°)
123288_328768 = 123288^2 + 328768^2 (°)
876712_328768 = 876712^2 + 328768^2 (°)

---------------------------------------------------

L = 14 (7 pairs)

0004860_0220401 = 0004860^2 + 0220401^2
9995140_0220401 = 9995140^2 + 0220401^2
0060130_0773101 = 0060130^2 + 0773101^2
9939870_0773101 = 9939870^2 + 0773101^2
0099010_0990100 = 0099010^2 + 0990100^2
9900990_0990100 = 9900990^2 + 0990100^2
0768180_2663025 = 0768180^2 + 2663025^2
9231820_2663025 = 9231820^2 + 2663025^2 (°)
0889680_2846976 = 0889680^2 + 2846976^2
9110320_2846976 = 9110320^2 + 2846976^2 (°)
1379310_3448276 = 1379310^2 + 3448276^2 (°)
8620690_3448276 = 8620690^2 + 3448276^2 (°)
1534830_3604525 = 1534830^2 + 3604525^2 (°)
8465170_3604525 = 8465170^2 + 3604525^2 (°)

---------------------------------------------------

Lengths 4, 6, 10, 12 and 14 only yield composites, alas. When I have the time I'll explore longer numbers. The solution marked with (°) are genuine as they don't need leading zero's."

***

Can someone explain the Patrick's observations about this kind of numbers?

***

One day after(21/08/2000) Patrick sent this:

Also I'll reproduce my program with which I did the search. This version is 'prepared' to look for L=16 ! I guess it is nothing earth-shattering, just straightforward code ready to scan the numbers. The program is standalone and tailor-made for the sums of squares and cannot be amended for the other cases of puzzle 104.

***

The 22/08/2000 Mahmoud Chilali solved the "sum of squares" problem and the Patrick's observations about them. Here is his interesting proof:

I solved the "sum of squares" case. In particular: there are infinitely many numbers that are the sum of their halves squares. More precisely: there exists a number of 2m digits that is the sum of its halves squares if and only if 10^{2m} +1 is not prime. Note that 10^{2*m}+1 is composite if m is not a power of two. This resembles Fermat numbers!

If a number is the sum of halves squares x^2+y^2, then so is the number obtained by replacing x with 10^m-x (where m is half the number of digits of the full number).

The problem amounts to finding pairs x and y such that b*x + y = x^2 +y^2, where b=10^m, 0<x<b, 0<y<b. If leading zeros are not allowed, then x must have exactly m digits, so x>=10^{m-1}=b/10. the equation above can be rewritten as (2y-1)^2 + (2x-b)^2 = b^2 + 1. As a result, if (x,y) i a solution, then so is (b-x, y) , which explains Patrick's remark. We can thus reduce the search to (x,y) such that 2x>=b.

The problem amounts to finding a decomposition of b^2+1 as the sum of two squares, with some conditions on the numbers (the conditions on x and y). Let us write b^2+1 = u^2+v^2 where u is odd and v is even (remember that b is even), and both ar >=0. now let us translate the conditions on (x,y) to conditions on u and v. we should have: u=abs(2y-1) ad v=2x-b. we have 0 <= v < b and 0<=u<2b-1. however, u^2 = b^2+1-v^2 shows that u<=b. it is easy to see that v=0 is impossible, and since u is odd, u>=1.

We end with the problem: find integers u and v, such that 1<=u<b, 1<=v<b, such that b^2+1=u^2+v^2.
* If b^2+1 is prime, then the only way to write it as the sum of two squares is b^2+1^2. so there is no u and v satisfying the above. Hence, there is no corresponding x and y.
* If b^2+1 is not prime, it may be written as the product of two integers, that are themselves the sums of two squares: b^2+1 = (t^2+s^2)(f^2+g^2). This is true since all the prime divisors of b^2+1 are of the form 4k+1 (-1 is a square modulo these primes). We can assume (t^2+s^2) <= b (if both member were > b, then their product would be >= (b+1)^2 > b^2+1). From this representation, one can write b^2+1 = (t*f + s*g)^2 + (t*g - s*f)^2 = (t*f - s*g)^2 + (t*g + s*f)^2 and derive u and v, and finally x and y. The sought number is then N=(2y-1)^2+(2x-b)^2=(b^2+1+u+vb)/2. for N to be prime, u must be =1 modulo 4 (otherwise, N is even).

Algorithm to find a number of 2m digits satisfying the condition (sum of squares):

- compute X = 10^{2m} +1.
- start with d=2
- y = sqrt(X - d^2). if d^2+y^2=X, derive a solution. else do nothing
- if d>=y, stop (if no solutions found, then X is prime)
- d =d +1. retry.

an example (yet to be checked though):

L=16:
50000340_00021648
50017522_00012717
50017114_00013261
and the symmetric ones (x -> 10^8 -x).

Generalization:

- find numbers that are the sums of the squares of their third parts.
- more generally, find numbers that are the sum of squares of their n-th parts.
In fact, for n>3, no solution exists. indeed, the problem may be written sum_{k=0,..., n-1} {x_k*b^k} = sum {x_k^2}. but the latter term is <= n*(b-1)^2, while the left hand one is >= b^{n-1} > n*(b-1)^2 for n>=4. for the case n=3, we can use the same method to end with: 1+b^2+b^4 = u^2 + v^2 + w^2, where u=2z-1, v=abs(2y-b) and w=b^2-2x. the sought number is then x^2+y^2+z^2 = x*b^2 + y*b +z. note that we still have the symmetry property: y may be replaced with b-y. What are the exact conditions that guarantee the existence of u,v and w satisfying the above (with the bound conditions: 0<= x,y,z <b, x>b/10 if leading zeros are not allowed....).

***

The 23/08/2000 I received two very interesting communications from Chris Nash, both related to the "sum of squares of two halves", providing more light about this part of the puzzle:

"I have some explanations about Patrick de Geest's results from his search for numbers that are 'squares of two halves'. Let the number be of length 2n digits, let the first n digits be a, and the second n digits be b. Then we have

a.10^n + b = a^2 + b^2

rearranging

a^2 - a.10^n - b + b^2 =0.

Choose a value for b, and view this as a quadratic equation in a. Remember that if x^2-Sx+P is a quadratic equation, the sum of the roots is S, and the product is P.

So in this case the sum of the roots for a is 10^n. In other words, for a given value of b, if solutions a exist, they come in pairs that sum to 10^n. Note also that the product of the roots is b^2-b, or b(b-1). This gives us a very quick way to check solutions - for instance it is not difficult to show that 12*88=33*32, and so 1233, 8833 are four-digit solutions. Note there is a way to check for a number being of the form b(b-1). Multiply it by 4, and add 1 - the result should be a perfect square (of 2b-1).

Now to use this in a search. We need to choose n, and vary a. For each a value calculate X=4(10^n-a)a+1 and check if it is a perfect square.

There are very fast ways to quickly check if a number is *not* a perfect square, by considering its value modulo a prime number and checking the quadratic residue symbol. But note there are some very quick things we can determine, for example, we can tell what is the last digit of this expression for each last digit of a, and quickly see whether it can ever be a perfect square. For example, it is not possible for the last digit of a to be 1, 4, 6, or 9 - in those cases, X ends in a 7, and so cannot be a square."

***

I recall the attention of the readers that these gentlemen (Patrick, Mahmoud & Chris) has only tackled one part of the whole puzzle. So many other interesting things should come in the near future...

***

***

***

Chris Nash provides (28/09/2000) a precision of his own formula for the number of solutions of length L:

***

As a matter of fact this precision was developed by Chris to solve a question of Patrick who only could discover with his code two pair of solutions instead of the three predicted by the old Chris's formula. Chris revised the original formula and modified as seen but the pairs remain being 3. Then he discovered the third (lost) solution which served at the same time for the discovering of a bug if the line 20 of the Patrick's code.

Here are the solutions for L=18:

Giovanni Resta came up with direct answers to questions about the infinitude of solutions (Nov. 2006):

Hi, apparently nobody answered the part 1 & 2 of your puzzle 104, i.e.,
proving that there are infinite numbers equal to the sum of the cubes of
their third parts, and finding prime such numbers greater than 10^10.

1) It is sufficient to notice that all the numbers of the form
[4][0][7] [34][00][67] [334][000][667] and so on have that property.
since 3333...4 can be expressed as (10^k+2)/3 and
6666...7 as (2*10^k+1)/3 it is sufficient to prove that
[(10^k+2)/3]^3 + [(2*10^k+1)/3]^3 = [(10^k+2)/3]*10^(2k) + [(2*10^k+1)/3]
which is just a matter of a little manipulation.

There are also other such infinite families, for example,
[34][10][67], [3334][0100][6667], [333334][001000][666667], etc.
where the inner part grows by a factor of 10, while the extremal
parts gain 2 digits each at each step.

2) I've checked all the numbers up to 15 digits.
The only primes I found are:

333366670001 = 3333^3 + 6667^3 + 0001^3

8740609620419 = 874^3 + 06096^3 + 20419^3
56482546234141 = 5648^3 + 25462^3 + 34141^3
127684145437883 = 12768^3 + 41454^3 + 37883^3

It is not too difficult to find a larger prime, exploiting one
of the infinite families found in point (1)
(several of which unfortunately only provide multiples of 3).

The numbers of the form [3334][0000][6667] we considered above
are never prime, because of their property.
Indeed, they are equal to [(10^n+2)/3]^3 + [(2*10^n+1)/3]^3.
And since in general x^3+y^3 = (x+y)(x^2-xy+y^2), they
have always at least two factors.

Another infinite family is that which contains numbers like
[3][7][1], [33][67][01], [333][667][001], where a(k) will have 3*k digits.
I'v checked a(n) for n<1000 and it is prime for n=3, 4 (as we already
know) and for n=46, which will provide a nice, certified, prime of 46*3 = 138 digits.

***