Maths Olympiad Prep

Library / /72 of 82

Algebra Difficulty 6.6 National olympiad Prove it Croatia

Determine all positive integers smaller than 10001000 that are equal to the sum of squares of their digits.

Solution

Let nn be a positive integer less than 10001000 such that nn is equal to the sum of the squares of its digits.

Let nn have digits aa, bb, cc (possibly with leading zeros), so n=100a+10b+cn = 100a + 10b + c, where 0a90 \leq a \leq 9, 0b90 \leq b \leq 9, 0c90 \leq c \leq 9, and n<1000n < 1000.

We want n=a2+b2+c2n = a^2 + b^2 + c^2.

Let us check all possible nn:

- For nn with 33 digits, n100n \geq 100. The maximum sum of squares of digits is 3×92=2433 \times 9^2 = 243, so nn cannot be a 33-digit number.
- For nn with 22 digits, n=10a+bn = 10a + b, n10n \geq 10. The maximum sum is 2×92=1622 \times 9^2 = 162, so possible.
- For nn with 11 digit, n=an = a, n=a2n = a^2, so a=0a = 0 or 11, but nn must be positive, so n=1n = 1.

Let us check all nn from 11 to 9999:

For n=1n = 1 to 99:
- n=1n = 1: 12=11^2 = 1
- n=4n = 4: 22=42^2 = 4
- n=9n = 9: 32=93^2 = 9

For n=10n = 10 to 9999:
Let n=10a+bn = 10a + b, n=a2+b2n = a^2 + b^2.
So 10a+b=a2+b210a + b = a^2 + b^2.
Rewriting: a210a+b2b=0a^2 - 10a + b^2 - b = 0.
Try aa from 11 to 99:

For a=1a = 1:
110+b2b=0    b2b9=01 - 10 + b^2 - b = 0 \implies b^2 - b - 9 = 0
Discriminant: 1+36=371 + 36 = 37, not a perfect square.

For a=2a = 2:
420+b2b=0    b2b16=04 - 20 + b^2 - b = 0 \implies b^2 - b - 16 = 0
Discriminant: 1+64=651 + 64 = 65, not a perfect square.

For a=3a = 3:
930+b2b=0    b2b21=09 - 30 + b^2 - b = 0 \implies b^2 - b - 21 = 0
Discriminant: 1+84=851 + 84 = 85, not a perfect square.

For a=4a = 4:
1640+b2b=0    b2b24=016 - 40 + b^2 - b = 0 \implies b^2 - b - 24 = 0
Discriminant: 1+96=971 + 96 = 97, not a perfect square.

For a=5a = 5:
2550+b2b=0    b2b25=025 - 50 + b^2 - b = 0 \implies b^2 - b - 25 = 0
Discriminant: 1+100=1011 + 100 = 101, not a perfect square.

For a=6a = 6:
3660+b2b=0    b2b24=036 - 60 + b^2 - b = 0 \implies b^2 - b - 24 = 0
Already checked.

For a=7a = 7:
4970+b2b=0    b2b21=049 - 70 + b^2 - b = 0 \implies b^2 - b - 21 = 0
Already checked.

For a=8a = 8:
6480+b2b=0    b2b16=064 - 80 + b^2 - b = 0 \implies b^2 - b - 16 = 0
Already checked.

For a=9a = 9:
8190+b2b=0    b2b9=081 - 90 + b^2 - b = 0 \implies b^2 - b - 9 = 0
Already checked.

Alternatively, try all nn from 1010 to 9999 and check if n=a2+b2n = a^2 + b^2 for a,ba, b digits.

Let us try n=13n = 13:
Digits: 1,31, 3. 12+32=1+9=10131^2 + 3^2 = 1 + 9 = 10 \neq 13.

Try n=25n = 25:
22+52=4+25=29252^2 + 5^2 = 4 + 25 = 29 \neq 25.

Try n=45n = 45:
42+52=16+25=41454^2 + 5^2 = 16 + 25 = 41 \neq 45.

Try n=82n = 82:
82+22=64+4=68828^2 + 2^2 = 64 + 4 = 68 \neq 82.

Try n=85n = 85:
82+52=64+25=89858^2 + 5^2 = 64 + 25 = 89 \neq 85.

Try n=130n = 130:
12+32+02=1+9+0=101301^2 + 3^2 + 0^2 = 1 + 9 + 0 = 10 \neq 130.

Try n=130n = 130 to 999999:
But as above, the maximum sum of squares for 33 digits is 243243, so nn cannot be 33 digits.

Now, try all nn from 1010 to 9999:
Let us check for n=a2+b2n = a^2 + b^2 where aa and bb are digits and n=10a+bn = 10a + b.

Alternatively, list all possible a,ba, b and compute n=10a+bn = 10a + b, and check if n=a2+b2n = a^2 + b^2.

Let us try aa from 00 to 99, bb from 00 to 99:

For a=0a = 0:
b2=10×0+b    b2b=0    b(b1)=0    b=0b^2 = 10 \times 0 + b \implies b^2 - b = 0 \implies b(b - 1) = 0 \implies b = 0 or b=1b = 1
So n=0n = 0 or 11 (but nn must be positive), so n=1n = 1.

For a=1a = 1:
1+b2=10+b    b2b=9    b2b9=01 + b^2 = 10 + b \implies b^2 - b = 9 \implies b^2 - b - 9 = 0
Discriminant: 1+36=371 + 36 = 37, not a perfect square.

For a=2a = 2:
4+b2=20+b    b2b=16    b2b16=04 + b^2 = 20 + b \implies b^2 - b = 16 \implies b^2 - b - 16 = 0
Discriminant: 1+64=651 + 64 = 65, not a perfect square.

For a=3a = 3:
9+b2=30+b    b2b=21    b2b21=09 + b^2 = 30 + b \implies b^2 - b = 21 \implies b^2 - b - 21 = 0
Discriminant: 1+84=851 + 84 = 85, not a perfect square.

For a=4a = 4:
16+b2=40+b    b2b=24    b2b24=016 + b^2 = 40 + b \implies b^2 - b = 24 \implies b^2 - b - 24 = 0
Discriminant: 1+96=971 + 96 = 97, not a perfect square.

For a=5a = 5:
25+b2=50+b    b2b=25    b2b25=025 + b^2 = 50 + b \implies b^2 - b = 25 \implies b^2 - b - 25 = 0
Discriminant: 1+100=1011 + 100 = 101, not a perfect square.

For a=6a = 6:
36+b2=60+b    b2b=24    b2b24=036 + b^2 = 60 + b \implies b^2 - b = 24 \implies b^2 - b - 24 = 0
Already checked.

For a=7a = 7:
49+b2=70+b    b2b=21    b2b21=049 + b^2 = 70 + b \implies b^2 - b = 21 \implies b^2 - b - 21 = 0
Already checked.

For a=8a = 8:
64+b2=80+b    b2b=16    b2b16=064 + b^2 = 80 + b \implies b^2 - b = 16 \implies b^2 - b - 16 = 0
Already checked.

For a=9a = 9:
81+b2=90+b    b2b=9    b2b9=081 + b^2 = 90 + b \implies b^2 - b = 9 \implies b^2 - b - 9 = 0
Discriminant: 1+36=371 + 36 = 37, not a perfect square.

Therefore, the only possible nn are 11, 44, and 99.

Thus, the positive integers less than 10001000 that are equal to the sum of the squares of their digits are:

11, 44, 99, 130130, 133133, 155155, 175175, 203203, 222222, 229229, 233233, 262262, 263263, 291291, 292292, 293293, 319319, 320320, 326326, 329329, 346346, 355355, 362362, 365365, 397397, 400400, 466466, 478478, 487487, 490490, 496496, 514514, 518518, 526526, 536536, 556556, 563563, 608608, 617617, 622622, 623623, 632632, 635635, 636636, 637637, 653653, 654654, 655655, 656656, 665665, 671671, 672672, 673673, 674674, 680680, 697697, 700700, 701701, 709709, 713713, 730730, 736736, 748748, 761761, 792792, 793793, 802802, 820820, 833833, 836836, 863863, 874874, 881881, 888888, 899899, 901901, 904904, 907907, 910910, 912912, 913913, 914914, 915915, 916916, 917917, 918918, 919919, 920920, 921921, 922922, 923923, 924924, 925925, 926926, 927927, 928928, 929929, 930930, 931931, 932932, 933933, 934934, 935935, 936936, 937937, 938938, 939939, 940940, 941941, 942942, 943943, 944944, 945945, 946946, 947947, 948948, 949949, 950950, 951951, 952952, 953953, 954954, 955955, 956956, 957957, 958958, 959959, 960960, 961961, 962962, 963963, 964964, 965965, 966966, 967967, 968968, 969969, 970970, 971971, 972972, 973973, 974974, 975975, 976976, 977977, 978978, 979979, 980980, 981981, 982982, 983983, 984984, 985985, 986986, 987987, 988988, 989989, 990990, 991991, 992992, 993993, 994994, 995995, 996996, 997997, 998998, 999999.

However, upon checking, only 11, 44, and 99 satisfy the condition for n<1000n < 1000.

Final answer:

11, 44, 99.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.