Iterated digits squaring - Rosetta Code

[david_uwi]

It will not work after 13 digits because 81*13 >1000.
I was assuming that after the first iteration the numbers were <1000.

Code: QB64: [Select]

1.     FOR i = 1 TO pp
2.         IF xa(i) <> 0 THEN
3.             z1 = i
4.             DO
5.                 d=0
6.                 if z1>1000 then z1=z1-1000:d=1
7.                 a = z1 \ 100
8.                 z1 = z1 MOD 100
9.                 b = z1 \ 10
10.                 c = z1 MOD 10
11.                 z1 = a * a + b * b + c * c + d
12.                 IF z1 = 89 THEN m89 = m89 + xa(i): EXIT DO
13.                 IF z1 = 1 THEN m1 = m1 + xa(i): EXIT DO
14.             LOOP
15.         END IF
16.     NEXT i

Change the loop near the end that checks the numbers after the first iteration

I like these problems that cannot easily be "brute forced".
The trick with this one is that after the first iteration the all the numbers are reduced to 3 digits (or less).
So the program calculates these. Many of the original n-digit numbers will give the same value after the first iteration.
So instead of using the digits 1-9 you start with the square of these 1,4,9,16...
Then build up the (squares of) two digit numbers by combining all permutation of the one digit numbers.
Then build up the 3 digit numbers by combining the 2-digit with the one digit and so on.
Then add them all up. then check the <=3 digit number for 89 convergence (without using strings -because these are slow).

[david_uwi]

Ah rookie mistake there on line 6. It should (of course) be >999 (not >1000)

[bplus]

@david_uwi  thanks for more clues in reply #15 and your fix for for going beyond 13 digits worked fine.

[david_uwi]

There is actually no need for the outer loop (for ndigits =1 to 19).
The matrix ib contains all the information. ib(x,1) contains all the 1 digit numbers, ib(x,2) all the two digit numbers..
ib(x,9) all the nine digit numbers. So to get up to 5 digits add ib(x,1)+ib(x,2)+ib(x,3),ib(x,4)+ib(x,5).
When I say 5 digit I mean 10000-99999.
So it might be even quicker! May even beat the C++, but as qb64 is converted to C before compiling this is not surprising.