Talk:First perfect square in base n with n unique digits: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (→Proof: Only N digits in base N) |
(optimizing suggestions) |
||
| Line 33: | Line 33: | ||
:Interesting in the abstract but not very useful. (I suppose the smallest such numbers aren't very useful either but... <shrug>) --[[User:Thundergnat|Thundergnat]] ([[User talk:Thundergnat|talk]]) 23:36, 22 May 2019 (UTC) |
:Interesting in the abstract but not very useful. (I suppose the smallest such numbers aren't very useful either but... <shrug>) --[[User:Thundergnat|Thundergnat]] ([[User talk: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.<BR> |
|||
First come into mind, that calculating strictly in the used base could be an advantage.<BR> |
|||
for n-> n+1 => n*n -> n*n + (2*n+1). If n*n is known than only addition to base is needed.<BR> |
|||
Squaring a number is easy by continiously doubling the number in base and add, if a bit of that number is set.<BR> |
|||
12 to base 13 : the digit 12 is 1100 in binary |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
Obviously 2n+1 -> 2(n+1)+1 = (2n+1)+2<BR> |
|||
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. |
|||
Revision as of 05:58, 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.