Talk:First perfect square in base n with n unique digits: Difference between revisions
Content added Content deleted
(→Space compression and proof ?: Added Python sketch of repeated digit sum function) |
|||
| Line 105: | Line 105: | ||
16 -> 404a9d9b -> f -> 1025648cfea37bd9 -> f |
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']</pre> |
['1', '4', '9', '1', 'a', '6', '4', '4', '6', 'a', '1', '9', '4', '1', 'f', '1', '4', '9', '1', 'a']</pre> |
||
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 chararacter) |
|||
<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) |
|||
# digit :: Int -> Char |
|||
def digit(n): |
|||
'''Digit character for given integer.''' |
|||
return '0123456789abcdefghijklmnopqrstuvwxyz'[n] |
|||
# 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> |
|||
Revision as of 11:45, 23 May 2019
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)
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:
- the repeated digit sum for each root and square,
- 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 chararacter)
<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)
- digit :: Int -> Char
def digit(n):
Digit character for given integer. return '0123456789abcdefghijklmnopqrstuvwxyz'[n]
- 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>