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

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 19:                     84C2B1GB9668FI4B8641GC1167BDF9² == 3AI6D3A2DA8DIA81C46G661H0GI2DB358724FB59E9CH21AFG60E1A4D0DIH
Base 20:                    9655G27F1B50133AG5AGIB9GC5I16HC² == 46EE97G32A654CIE49IGB500000000FGCJH813CD2A000000000000000000E9
Base 21:                   A5A4GA58DB9J5K2C4C14B908214756C7² == 5063DK4HA0B78D5KAIKB40345K19JF89AGCD4JE916I8B7277215F0BC04GC8904
Base 22:                  B0D611CBEG6I3K8ED18EG4K70FH70EA4G² == 5BD691HA2A1JG0JG59G4IFH2KH98LFK557F7396BJ65KHG1JI9081J3D23E3D63BGC
Base 23:                 BCKD3DBCA7KA3E32FD26G0AB8G317DLAK6² == 5IEKJCJKBHKI1J4ED24GBLLCFCM5FC5J3115L74H4D41LLFI9EEA6AK3B605HMFI4LC8
Base 24:                BJJB1AL6I37MH6CNJ3JEK6EBK4G9L97ECAG² == 5JK4EF03B223EJ153H6NC94B2BCA7E91HI0G4G1GF2CJDHHB08EC8M412J3F0JCAM7GL81
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 may be a perfect square, just as well since you say it is.
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)
Note that adding a zero to a number doesn't change it's digital root so the repeated digit can not be zero so 10123456789abcdefg must be the smallest candidate--Nigel Galloway (talk) 12:45, 25 May 2019 (UTC)
Many thanks for confirming that Nigel. I had in fact realized it was true when submitting my original Go entry but omitted to explain the reasoning and so, as Thundergnat rightly pointed out, it looked like I was using a 'magic number'. You're also right that it's not really acceptable to assume an extra digit for bases 13 and 17 without further explanation so in my latest Go submission I'm justifying this from first principles. --PureFox (talk) 17:08, 25 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)
Nigel, how would you formulate cases like base 12 and 14 in terms of quadratic residues ? The repeated digit sums of the first all-digit perfect squares seen for 12 and 14 are 'b' and 'd' respectively, corresponding to x^2 mod (N-1) == 0. Am I right in thinking that the 0 case is not usually treated as a member of the set of residuals ? Presumably we need to tack it on to our working lists of residuals here ... Hout (talk) 12:01, 24 May 2019 (UTC)
Scratch that – I see that you are already including such cases above in residuals base 16 -> 1 4 9 16 Hout (talk) 12:18, 24 May 2019 (UTC)

## analytically determine minimum start value

As a hint to other entry authors: here is how to easily determine a minimum start value analytically. This will work correctly for any base up to 36, but is kind of pointless below base 10 as brute force is probably faster than doing the calculation.

Note: I would not have figured this out without the above analysis by Hout and Nigel Galloway. Kudos to both of them.

Here is a Perl 6 script showing each step spelled out: Try it online!

```sub digital-root (\$root is copy, :\$base) {
\$root = \$root.comb.map({:36(\$_)}).sum.base(\$base) while \$root.chars > 1;
\$root.parse-base(\$base);
}

sub first-square (Int \$n) {
say '*' x 79;
say "Base \$n -- Uses the possible digits:";
say my @start = flat '1', '0', (2 ..^ \$n)».base(\$n);

say "\nDigital root of those digits: ",
my \$root  = digital-root( (^\$n)».base(\$n).join, :base(\$n) );

say "\nDigital roots of the first \$n numbers in base \$n:";
say my @roots = (1..^\$n).map(*²).map: { digital-root(\$_.base(\$n), :base(\$n) ) };

say "\nMinimum difference of {\$n}-digit root from one of the first \$n digital roots >= \$root:";
my \$offset = min(@roots.grep: * >= \$root ) - \$root;

print \$offset = \$offset > \$n ?? 0 !! \$offset.base(\$n);

if \$offset > 0 {
say "  ({\$root+\$offset} - \$root = \$offset)\n\nSo, at a minimum, the smallest starting value will need an extra \$offset";
@start[1+\$offset] = \$offset ~ @start[1+\$offset];
} else {
say "\n\nSo no extra digits should be necessary.";
}

say "Minimum start value: ", @start.join;

}

.&first-square for 17 .. 21;```

Which outputs:

```*******************************************************************************
Base 17 -- Uses the possible digits:
[1 0 2 3 4 5 6 7 8 9 A B C D E F G]

Digital root of those digits: 8

Digital roots of the first 17 numbers in base 17:
[1 4 9 16 9 4 1 16 1 4 9 16 9 4 1 16]

Minimum difference of 17-digit root from one of the first 17 digital roots >= 8:
1  (9 - 8 = 1)

So, at a minimum, the smallest starting value will need an extra 1
Minimum start value: 10123456789ABCDEFG
*******************************************************************************
Base 18 -- Uses the possible digits:
[1 0 2 3 4 5 6 7 8 9 A B C D E F G H]

Digital root of those digits: 17

Digital roots of the first 18 numbers in base 18:
[1 4 9 16 8 2 15 13 13 15 2 8 16 9 4 1 17]

Minimum difference of 18-digit root from one of the first 18 digital roots >= 17:
0

So no extra digits should be necessary.
Minimum start value: 1023456789ABCDEFGH
*******************************************************************************
Base 19 -- Uses the possible digits:
[1 0 2 3 4 5 6 7 8 9 A B C D E F G H I]

Digital root of those digits: 9

Digital roots of the first 19 numbers in base 19:
[1 4 9 16 7 18 13 10 9 10 13 18 7 16 9 4 1 18]

Minimum difference of 19-digit root from one of the first 19 digital roots >= 9:
0

So no extra digits should be necessary.
Minimum start value: 1023456789ABCDEFGHI
*******************************************************************************
Base 20 -- Uses the possible digits:
[1 0 2 3 4 5 6 7 8 9 A B C D E F G H I J]

Digital root of those digits: 19

Digital roots of the first 20 numbers in base 20:
[1 4 9 16 6 17 11 7 5 5 7 11 17 6 16 9 4 1 19]

Minimum difference of 20-digit root from one of the first 20 digital roots >= 19:
0

So no extra digits should be necessary.
Minimum start value: 1023456789ABCDEFGHIJ
*******************************************************************************
Base 21 -- Uses the possible digits:
[1 0 2 3 4 5 6 7 8 9 A B C D E F G H I J K]

Digital root of those digits: 10

Digital roots of the first 21 numbers in base 21:
[1 4 9 16 5 16 9 4 1 20 1 4 9 16 5 16 9 4 1 20]

Minimum difference of 21-digit root from one of the first 21 digital roots >= 10:
6  (16 - 10 = 6)

So, at a minimum, the smallest starting value will need an extra 6
Minimum start value: 10234566789ABCDEFGHIJK```

I've just tried to run a variation of my Go program using this approach up to base 21. However, I'm getting a lower value than your Perl 6 program for base 21 itself even though I'm starting from 10234566789ABCDEFGHIJK as you are, viz:

Base 21: 4C9HE5FE27F² == 1023457DG9HI8J6B6KCEAF

compared to your:

Base 21: 4C9HE8175DA² == 1023467JKAIEHB5DF9A8CG

Unless there's something wrong with Go's big.Int routines, both numbers check out as perfect squares when I convert them to decimal so I'm at a loss to explain the difference. --PureFox (talk) 00:20, 26 May 2019 (UTC)

Well, I think the simple explanation is that I screwed something up. When I run it again, I get the same thing you got, so I'm not sure where that came from. I must have saved a result from an interim version where I was still working out bugs and never went back and reverified it; which is pretty sad since 21 actually finishes very quickly. At any rate, you are correct, I have the wrong answer for base 21 right now. Fixing. --Thundergnat (talk) 02:32, 26 May 2019 (UTC)

The valid digital roots can be calculated using the following code in F#: <lang Fsharp>

``` let rSet g=set[for n in [0..g-1] do yield n*n%g]
```

</lang> rSet 20 -> set [0; 1; 4; 5; 9; 16]. Remember that this is base 20 and 0 corresponds to 20.
Similar code in Python is: <lang Python>

``` rSet=lambda g: {n*n%g for n in range(1,g)}
```

</lang> rSet(20) -> {0, 1, 4, 5, 9, 16}
--Nigel Galloway (talk) 17:02, 25 May 2019 (UTC)