Talk:First perfect square in base n with n unique digits

Leading zeros ?

Perhaps the 'First perfect square in base 2 with 2 unique digits' is arguably '01' ? Hout (talk) 23:53, 20 May 2019 (UTC)

Ok, kind of weaselly but fair point. Reworded; First perfect square in base 2 with 2 significant unique digits. --Thundergnat (talk) 01:17, 21 May 2019 (UTC)

Proof

The task conjectures that the sum from n=0 to some n of 2n+1 has at least one value of n for every base for which the sum is a number containing all digits in the base. Can you prove this conjecture?--Nigel Galloway (talk) 21:34, 22 May 2019 (UTC)

Prove? No. Or, at least, I can't. Though it is pretty easy to find perfect squares in bases 2 through 36 that contain 2 through 36 unique digits respectively. I have no reason to not believe that the same holds true for higher bases. Note that there is no constraint that the square in base N has only N digits; only that each digit from 0 to N-1 appears at least once. The challenge is in finding the smallest such number.

I ran this in the Perl 6 version for bases 17 through 36 searching arbitrarily large squares. Took less than 1/4 second to complete.

Base 17:                       5GFF91A47EFG754GBDEC9DB68GGG² == 21G3G8551E554G6B342BGF4018G54650E0GD189C01G6740EAE1CE7F4
Base 18:                      72255AD78158400C14341DF6HFDAG² == 2EC0BEFB6B45H67C948CEGDDB57707HEGD2D01F68A1675FH9967385HDA
Base 19:                     84C2B1GB9668FI4B8641GC1167BDF9² == 3AI6D3A2DA8DIA81C46G661H0GI2DB358724FB59E9CH21AFG60E1A4D0DIH
Base 20:                    9655G27F1B50133AG5AGIB9GC5I16HC² == 46EE97G32A654CIE49IGB500000000FGCJH813CD2A000000000000000000E9
Base 21:                   A5A4GA58DB9J5K2C4C14B908214756C7² == 5063DK4HA0B78D5KAIKB40345K19JF89AGCD4JE916I8B7277215F0BC04GC8904
Base 22:                  B0D611CBEG6I3K8ED18EG4K70FH70EA4G² == 5BD691HA2A1JG0JG59G4IFH2KH98LFK557F7396BJ65KHG1JI9081J3D23E3D63BGC
Base 23:                 BCKD3DBCA7KA3E32FD26G0AB8G317DLAK6² == 5IEKJCJKBHKI1J4ED24GBLLCFCM5FC5J3115L74H4D41LLFI9EEA6AK3B605HMFI4LC8
Base 24:                BJJB1AL6I37MH6CNJ3JEK6EBK4G9L97ECAG² == 5JK4EF03B223EJ153H6NC94B2BCA7E91HI0G4G1GF2CJDHHB08EC8M412J3F0JCAM7GL81
Base 25:               BK3HB0BCN4O23H621G29O4KE2DGIM1D0FECA² == 5E9C73HH28G8I5G5CA53F1000000000002MF6NDH4KLJOG6000000000000000000009BAD9
Base 26:              BD4HKMDK973KL4HH94HJ8M0JN109MP9MMD84G² == 52AGK7MKMH0ENMCJ3A6AJD1FL8PDMCABC9LBJM3EJ0878MHE9BK544L27HIA9G27GEBA2NOPP3
Base 27:             APJNIHGH3F61KI69MHEEEHIA9DC05K7MG6195K² == 4BQ6O8IQEI6B95D1AFEE6LBLAILJBQGPEQPOC7KLN0ONJH3KD1LGGI2H0FQ5QI2GNF3I09ENE3AM
Base 28:            A55IE6QOCHG0R55GF2H20LO8MDCM143NA0Q6M14² == 3JL07Q303FAFFH0JN6GAJBHBI6D06HB1HBFI4J1JB8H2KJCE5KK1N4C5D2IR1LLME8J1JO16N9A9OP
Base 29:           97D812BS18P64KPI624O0DL0BSAC0GK8NNDOMI2E² == 2RK4HI8MRD1LDMRC80H9HA6AOOQEH7CBI82GG5EDNOMM3912SLFJ0J8FP1MRBMF8FILB1021O80SPN3S
Base 30:          86MM394P48KQMQ728TTCLLO8S0M07R1C493QTTC3E² == 27JJDP5BJ77KKA8JJHOAJ8KSG61TA0Q0NL683LE5P6TOGO5MO0L28HEREF8INATMEDGOS3O4669BMK7C7F
Base 31:         74I06DPHJJNGO4NJM3KDNMNR897TEJU2G1M9CH6QL4² == 1K2P2D4IKE0P5HM89DL52H47K2NPT3AT1Q49EJ5KU6O13IPR077EGFDDI94TI2R8R6OCUI727SLB5LHP1S58
Base 32:        62F0FKJVUFL00000000000000000000000000000000² == 14TQ8V4O1QCCRV36UCRC6QOG2DO26JPVQUO8RKSGNHCVAC5OALRGD3PMIOGM4LB1AB4KILE9700000000001FH
Base 33:       51T5JT538NMJDB8TNGSG8U93DSDSGTI9A8HEGBKW4JIJ² == PIV84U6UKBBI09WIBK966BVQI3T6TMW8MKQ5929NEAI1ENKJLGB9FPU1OSTS6KB6GDUUN7RN6F852C67JHV491G
Base 34:      4431S5BXSONE2IXPWJGXOK8U5CVEPBBJRRKIXBAKI4NAG² == GX75B752G2S64UFUJ4L5BR3X3RSOGRNREHDXN472CD4INIVLLF1NKKEI6R9AH4SPOG3LQMP0UNXS80KMOWFTV7SI8
Base 35:     3A2U0DIKHQASF0FQ29TQ5TSSVF719C5ONHMVQJVPNB8CNK² == ASDRFOOC3068TDRBUSS1A65ITSTGV6V5392DVCAJAPONRVJU13E0H76ISWH34S2OOFOXYOM06RAAS6LGRGK98NQNBLB
Base 36:    2KJVULABXHKEQZQGYBM5INOYJ5OKGMNXF53URVDRT6EF5KW² == 6LXXRR9OJDK9NUEQQDF373MXEDKOPQYYRU5VPU6F1S5QRYWCPOKCNGQBE1ERAOK4DQWWGH4XKMM028MZB3I3TSGJ64IC9

Interesting in the abstract but not very useful. (I suppose the smallest such numbers aren't very useful either but... <shrug>) --Thundergnat (talk) 23:36, 22 May 2019 (UTC)

Actually, after a tiny bit of thought, I think I can prove it.

Base 2: Proof by demonstration. 10² == 100

Base N > 2: Concatenate the digits 1 to N-1, two zeros, then N zeros. Find the integer ceiling of the square root and square it. The resulting number will always start with the digits 1 to N-1 and zero. It almost definitely won't be the smallest such number but it proves that at least one number exists for any N. --Thundergnat (talk) 14:31, 23 May 2019 (UTC)

any ideas of optimizations ?

The main runtime for bases 2..16 ( 99% ) is used to find the one for base 13.
First come into mind, that calculating strictly in the used base could be an advantage.
for n-> n+1 => n*n -> n*n + (2*n+1). If n*n is known than only addition to base is needed.
Squaring a number is easy by continiously doubling the number in base and add, if a bit of that number is set.
12 to base 13  : the digit 12 is 1100 in binary

sq= 00 , n2 = 0C|12dec , bit0 = 0 
sq= 00 , n2 = 1B|24dec , bit1 = 0 
sq= 00 , n2 = 39|48dec , bit2 = 1 
+   39
sq= 39 , n2 = 75|48dec , bit3 = 1 
+   75
sq= B1 -> 11*13+1 = 144 == 12*12

Obviously 2n+1 -> 2(n+1)+1 = (2n+1)+2
Its a pitty that "carry := 0;if num >= base then num := num-base;Carry=1; " are not optimized to cmove in freepascal, like C or freebasic do. But the addition has mainly have the lenght of base conversion.

Space compression and proof ?

Not sure whether there is a provably reducible pattern here which might yield some more compression of the search space, but there is a literature on the necessary cyclicality of the repeated digit sums of perfect squares, and if there also turned out to be a pattern to the squared digit sum of *these* particular squares, it might be possible to divide the search space by the length of the digit sum cycle for a given base. For professional pattern searchers, the output of this problem is adorned for each base below with:

1. the repeated digit sum for each root and square,
2. a sample of the cycle of repeated digit sums for squares represented in that base (first 20 perfect squares)

Smallest perfect squares using all digits in bases 2-16,
with repeated digit sums for each root and square, and a sample of the digit sum cycle for squares represented in each base:

Base      Root    Square
 2 ->       10 ->  1 -> 100 -> 1
['1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1']

 3 ->       22 ->  2 -> 2101 -> 2
['1', '2', '1', '2', '1', '2', '1', '2', '1', '2', '1', '2', '1', '2', '1', '2', '1', '2', '1', '2']

 4 ->       33 ->  3 -> 3201 -> 3
['1', '1', '3', '1', '1', '3', '1', '1', '3', '1', '1', '3', '1', '1', '3', '1', '1', '3', '1', '1']

 5 ->      243 ->  1 -> 132304 -> 1
['1', '4', '1', '4', '1', '4', '1', '4', '1', '4', '1', '4', '1', '4', '1', '4', '1', '4', '1', '4']

 6 ->      523 ->  5 -> 452013 -> 5
['1', '4', '4', '1', '5', '1', '4', '4', '1', '5', '1', '4', '4', '1', '5', '1', '4', '4', '1', '5']

 7 ->     1431 ->  3 -> 2450361 -> 3
['1', '4', '3', '4', '1', '6', '1', '4', '3', '4', '1', '6', '1', '4', '3', '4', '1', '6', '1', '4']

 8 ->     3344 ->  7 -> 13675420 -> 7
['1', '4', '2', '2', '4', '1', '7', '1', '4', '2', '2', '4', '1', '7', '1', '4', '2', '2', '4', '1']

 9 ->    11642 ->  6 -> 136802574 -> 4
['1', '4', '1', '8', '1', '4', '1', '8', '1', '4', '1', '8', '1', '4', '1', '8', '1', '4', '1', '8']

10 ->    32043 ->  3 -> 1026753849 -> 9
['1', '4', '9', '7', '7', '9', '4', '1', '9', '1', '4', '9', '7', '7', '9', '4', '1', '9', '1', '4']

11 ->   111453 ->  5 -> 1240a536789 -> 5
['1', '4', '9', '6', '5', '6', '9', '4', '1', 'a', '1', '4', '9', '6', '5', '6', '9', '4', '1', 'a']
12 ->   3966b9 ->  b -> 124a7b538609 -> b
['1', '4', '9', '5', '3', '3', '5', '9', '4', '1', 'b', '1', '4', '9', '5', '3', '3', '5', '9', '4']

13 ->  3828943 ->  1 -> 10254773ca86b9 -> 1
['1', '4', '9', '4', '1', 'c', '1', '4', '9', '4', '1', 'c', '1', '4', '9', '4', '1', 'c', '1', '4']

14 ->  3a9db7c ->  d -> 10269b8c57d3a4 -> d
['1', '4', '9', '3', 'c', 'a', 'a', 'c', '3', '9', '4', '1', 'd', '1', '4', '9', '3', 'c', 'a', 'a']

15 -> 1012b857 ->  7 -> 102597bace836d4 -> 7
['1', '4', '9', '2', 'b', '8', '7', '8', 'b', '2', '9', '4', '1', 'e', '1', '4', '9', '2', 'b', '8']

16 -> 404a9d9b ->  f -> 1025648cfea37bd9 -> f
['1', '4', '9', '1', 'a', '6', '4', '4', '6', 'a', '1', '9', '4', '1', 'f', '1', '4', '9', '1', 'a']

A Python sketch FWIW, of a function from a given base and number to a repeated digit sum as an integer. (For bases above 10 course, you will also need a `digit` function from the sum to a digit character)

<lang python># repSum :: Int -> Int -> Int def repSum(base):

   Repeated sum of the digits of a number
      n in a given base.
   
   def f(x):
       m = 0
       while x:
           m = m + (x % base)
           x //= base
       return m

   def baseGT(n):
       return base > n

   def go(x):
       return until(baseGT)(f)(x)
   return lambda n: go(n)

1. digit :: Int -> Char

def digit(n):

   Digit character for given integer.
   return '0123456789abcdefghijklmnopqrstuvwxyz'[n]

1. until :: (a -> Bool) -> (a -> a) -> a -> a

def until(p):

   The result of repeatedly applying f until p holds.
      The initial seed value is x.
   
   def go(f, x):
       v = x
       while not p(v):
           v = f(v)
       return v
   return lambda f: lambda x: go(f, x)</lang>

The first pattern that jumps to the eye, after the self-evidences of bases 2 and 3, is that:

1. The digit sum cycles for a given base are symmetric – a series of digits is repeatedly followed by its reflection.
2. Where there is a single cycle of reflection/symmetry, and only one digit that is repeatedly flanked by twin siblings, that digit will also be the repeated digit sum of the first digit-saturating perfect square (square that needs all digits in the base) that we encounter.
3. The picture is subtler or more obscure in the rarer cases where there are multiple symmetries in the digit sum cycle – more than one digit which is repeatedly flanked by identical twins. Such is, perhaps not accidentally, the case of base 13, which is also consuming the most processor time here. (For base 13, we repeatedly see both '1', 'c', '1', and '4', '9', '4', and the first digit-saturation that we (eventually) find occurs at a point where the digit sum is 1 ...

Any conjectures ? Hout (talk) 17:40, 23 May 2019 (UTC)

Excellent. This reminded me of Digital root and Casting out nines. The Digital Root of a perfect square expressed in base n is a quadratic residual in base n-1. The quadratic residuals in base 9 are 1, 4, and 7. 0 is treated as 9 so 1+2+3+4+5+6+7+8+9 -> 45 -> 9 so there may be a 10 digit perfect square using all the digits in base 10. Just as well since we've found one. So for base 13 the digital root of a perfect square must be 1, 4, 9, or 12. 1+2+3+4+5+6+7+8+9+a+b+c -> 60 -> 6. So any time spent looking for a 13 digit perfect square using all the 13 digits in base 13 has been wasted. I can also determine which digits to repeat when looking for a 14 digit perfect square. To check 1+0+2+5+4+7+7+3+c+a+8+6+b+9 -> 67 -> 10 -> 1.--Nigel Galloway (talk) 20:48, 23 May 2019 (UTC)

Good ! Someone with a bit of mathematical culture. I wish I had some :-) Hout (talk) 21:07, 23 May 2019 (UTC)

I have tentatively identified a candidate for the smallest base 17 number. (Still have not completed an exhaustive search of 17 digit numbers.) It would be interesting to see if the below fits in with your conjecture. --Thundergnat (talk) 23:19, 23 May 2019 (UTC)

  Base 17:  423F82GA9² == 101246A89CGFB357ED

The residuals base 16 are 1 4 9 16
0+1+...+15+16 -> 80 -> 8 therefore no 17 digit perfect square made from digits 0..g in base 17 so searching for one is pointless.
101246A89CGFB357ED -> 81 -> 9 therefore is a perfect square.
smallest possible number made repeating 1 is 10123456789abcdefg so you only need to verify that there is no perfect square between 10123456789abcdefg and 101246A89CGFB357ED which contains all the digits between 0 and g to prove that 101246A89CGFB357ED is the smallest.--Nigel Galloway (talk) 10:07, 24 May 2019 (UTC)

So digital root 9, I think, drawn from the dual-symmetry base 17 cycle for perfect squares of

           [ '1', 'g', '1', '4', '9', 'g', '9', '4', '1', 'g', '1']

base 13 (digital root 1 for the first match), also has a dual-symmetry cycle.

Conceivable that there is some kind of congruence there ?:

         #       '1', 'g', '1', '4', '9', 'g', '9', '4', '1', 'g', '1'  base 17  (digital root 9 for that candidate)
         #                            *         *
         #            '4', '9', '4', '1', 'c', '1', '4', '9', '4'       base 13  (digital root 1 for the first match found)

Hout (talk) 23:59, 23 May 2019 (UTC)