Talk:Steady squares

From Rosetta Code
Revision as of 15:07, 14 October 2022 by Enter your username (talk | contribs) (→‎Reduce search range by observation of the results: Added syntaxhighlight tag on pascal code snippet.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Reduce search range by observation of the results

By taking a look at the results,I tried to search for results by prepending a digit to n.
And there comes the solution:By prepending a digit to n, than n*n must end in n to be a steady square.
So only solutions of one digit before can be solutions.

function CalcSquare(n:LongInt;Pot10:byte);
//pot10 is 10^(count of digits of n -1)
//prepend one digit to n  
  dgt: LongInt;
    //ex.: n= 5,Pot10 = 1, dgt= 2;-> n2= (2*10*1+5)^2 = 625
  For dgt := 1 to 9 do
    // n= 5 , dgt= 2*10 -> n2= 625
    n2 = sqr(dgt*10*Pot10+n);   
    n2 = dgt*dgt*100*Pot10*Pot10+2*dgt*10*pot10*n+n*n;
// term: dgt*dgt*100*Pot10*Pot10+2*dgt*10*pot10*n// always has ends in Pot10+1 "0" digits
// so n*n must end in n, to be a steady square
Note also that it must end in 1,5 or 6 (not 0 as any number ending in 0 squared ends with twice as many zeros).--Nigel Galloway (talk) 12:46, 21 December 2021 (UTC)
Ah, you beat me to it (I posted my Phix entry before reading this). I was hopeful, as you (Horst) seem to suggest, that we only have to look at the k-1 digit solutions on each iteration, and that way maybe even find all possible such numbers there could ever be, that is if any iteration found none we'd be done, but alas zero-fill totally spanners that illusion (eg 90625 off the back of 625). Oh, unless I've missed a logical reason why it is not worth checking (eg) 1001 or (say) 900625... Then again the series could be and probably is infinite anyway. --Pete Lomax (talk) 14:53, 21 December 2021 (UTC)
Nevermind that last bit:
1000557423423230896109004106619977392256259918212890625^2 = 10011151575673345586...92256259918212890625 (109 digits)
is a triple-zero-fill, and I've found examples all the way up to (a quite random) 548 digit n with a 1096 digit square. --Pete Lomax (talk) 15:49, 21 December 2021 (UTC)
Pete you were right.My first thought was, there where only a finite set of steady squares.
Thanks for showing, that prepending 1..x zeros ( and increasing Pot10 the same way ) to n, which is generating a stead square, lets n*n still be a steady square.
I am happy for not writing "proof" ;-) --Horst.h (talk) 10:32, 22 December 2021 (UTC)

Why not 1001 or 900625

Consideration of this question leads to an improvement of the algorithm. Consider a number of the form g2g1g0. Uncontentiously I assert that g0 is 1, 5 or 6. Prepending n=0..9 to each and squaring these to obtain xg1g0 and filtering for g1=n, I obtain 01, 25, 76 which are candidates for the next iteration. Note that using n=0 for g0=5 excludes 05 because 0 does not equal 2 and that it is only necessary to check g1 against n. Extending for g3 makes the candidate list 001, 625, and 376. At g4 interestingly 0625 is included because g4 in 390625 passes g4=n for n=0. Note 00625 will fail at the next iteration, thus eliminating 900625.

Considering g0=1 and gn-1..g1=0

  101*    201*     1001*
  101     201      1001
-----     ---      ----
  101+    201+     1001+
10100   20200   1001000
-----   -----   -------
10201=  20401=  1002001=

Then gn is always 2n%10 which never equals n.--Nigel Galloway (talk) 14:15, 23 December 2021 (UTC)

Excellent stuff. Likewise on the latter point we cannot "zero-fill" the single digit g0=5 or g0=6 because g1 can never be 0. Going back to the first paragraph, another way to say that (as a guide rather than a proof) might be, using the triple-zero-fill example above:
    55742..90625^2 = ...6100055742..90625
100055742..90625^2 = ...1100055742..90625
The three zeros in the first line make it a zero-fill candidate for three rounds, after which the second line will either "take over the mantle" in the list of potential candidates, or there won't be anything that does. Or it might be more accurate to say it only becomes a candidate in three rounds time?
From my experiments so far ... Oh, ffs, off course, how did I not spot that? It is just a 5-chain and a 6-chain, with the 1-chain dying instantly. There will only ever be and always will be either one or two n-digit steady square numbers ending in 5 or 6 or both, maybe with the odd skip when both leap-frog. Apart from the first three, there will never be three steady squares of the same length, and if there are two, then one will end in 5 and the other in 6. DOH. I will however leave it up to someone else to come up with a proof that there will always be a single prefix digit that will work, for each chain. --Pete Lomax (talk) 02:05, 24 December 2021 (UTC)
It is also necessary to prove that there is only one digit that satisfied the requirement. That is the chains do not branch.--Nigel Galloway (talk) 19:51, 26 December 2021 (UTC)

No Search Required

I introduce a table:

          for g0=5   for g0=6
(n+g)%10   gn         gn
    0      0          0
    1      1          9
    2      2          8
    3      3          7
    4      4          6
    5      5          5
    6      6          4
    7      7          3
    8      8          2          
    9      9          1

Starting with g0=6 I let g=0 and n=g0*g0/10=3. Looking up 3 in the table g1=7. I let n=(n+g+2*g1*g0)/10=8, g=g1*g1=49. Looking up 7 in the table g2=3. I let n=(n+g+2*g2*g0)/10=9, g=g2*g1+g1*g2=42. Looking up 1 in the table g3=9. I let n=(n+g+2*g3*g0)/10=15, g=g3*g1+g2*g2+g1*g3=135. Looking up 0 in the table g4=0. I let n=(n+g+2*g4*g0)/10=15, g=g4*g1+g3*g2+g2*g3+g1*g4=54. Looking up 9 in the table g5=1. .... and so to infinity and beyond.

Starting with g0=5 I let g=0 and n=g0*g0/10=2. Looking up 2 in the table g1=2. I let n=(n+g+2*g1*g0)/10=2, g=g1*g1=4. Looking up 6 in the table g2=6. I let n=(n+g+2*g2*g0)/10=6, g=g2*g1+g1*g2=24. Looking up 0 in the table g3=0. I let n=(n+g+2*g3*g0)/10=3, g=g3*g1+g2*g2+g1*g3=36. Looking up 9 in the table g4=9. I let n=(n+g+2*g4*g0)/10=12, g=g4*g1+g3*g2+g2*g3+g1*g4=36. Looking up 8 in the table g5=8. .... and so to infinity and beyond.

The existence of this table and method proves that these two sequences are infinite and unique.--Nigel Galloway (talk) 19:30, 26 December 2021 (UTC)

Agreed and well done! Phix entry added. --Pete Lomax (talk) 15:17, 31 December 2021 (UTC)

RC's First Interesting Fact for 2022

With the exception of g0 where 5 -> 6 if you tell me the nth digit in the 5 sequence, I can tell you the nth digit in the 6 sequence using the following mapping:

0 -> 9
1 -> 8
2 -> 7
3 -> 6
4 -> 5
5 -> 4
6 -> 3
7 -> 2
8 -> 1
9 -> 0

--Nigel Galloway (talk) 16:11, 3 January 2022 (UTC)

Yes, the digits sum up to 9 in Steady_Squares#Some_Examples for 80 digits without the last digit --Horst.h (talk) 16:41, 3 January 2022 (UTC)

For each digit of the 5-series and 6-series (for the same number of digits), the first through the next-to-last digits (when present) sum up to 9, the final (ones) digit sums to 11.
for single digit, (10^1): 5 + 6 = 11
for double digits, (10^2): 25 + 76 = 101
for triple digits, (10^3): 625 + 376 = 1001
...pattern continues...
So the 6-series (for any number of digits) can be obtained by subtracting the 5 series result (for that number of digits) from 10^(number of digits), then adding 1.
For four digits (and a few others) the leading digit of the 5-series is a zero, so the 6-series result is 10001 - 0625 = 9376.
When the first digit of the 5-series result is 9 (such as 90625), the corresponding 6-series result is a repeat of the previous number of digits (such as 9376), since the leading digit of the 6-series is zero.

--Enter your username (talk) 05:39, 5 January 2022 (UTC)