mersenneforum.org August 2022
 Register FAQ Search Today's Posts Mark Forums Read

 2022-08-02, 09:55 #1 tgan   Jul 2015 2×19 Posts August 2022 Last fiddled with by tgan on 2022-08-02 at 09:57
 2022-08-09, 19:52 #2 dg211   Jun 2016 22×7 Posts The solver list got updated yesterday, so looks like I've just missed it and will have to wait for official verification of my solution. Can someone please tell me if these last three digits are correct? 399 for 2^24 499 for 2^256
 2022-08-10, 02:14 #3 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 3·23·149 Posts Is this question asked after submitting, or before submitting? Can you prove?
 2022-08-10, 08:47 #4 dg211   Jun 2016 111002 Posts I haven't submitted my answer yet, I only got it yesterday. I just didn't want to have to wait for the next update to find out if I'm wrong. These are my full numbers for all the other n apart from 24 and 256, if that helps convince you (ignore the third column). 3, 17342172, 25521 4, 1949859552, 48572 5, 830366532, 72407 6, 617933898, 94568 7, 2484449895, 119359 8, 386349543, 142862 9, 1713834966, 172932 10, 2571134958, 194433 11, 1022314413, 213965 12, 2608264098, 236454 13, 188754042, 256695 14, 750264864, 280474 15, 2001418431, 300141 16, 2061221547, 319716 17, 2000492208, 340267 18, 1987520109, 359849 19, 1032518811, 379478 20, 3031127838, 398842 21, 1035351822, 418322 22, 1467953748, 438110 23, 1068900021, 457830 25, 2995505946, 497266 26, 2956941426, 517137 27, 2383350363, 536523 28, 1021560798, 555614 29, 2712875607, 575822 30, 2576450757, 595383 31, 325091946, 614417 32, 3131054478, 633408 33, 1398089298, 652478 34, 1669034772, 671533 35, 2516387778, 690717 36, 1488878688, 709799 37, 1945001943, 728957 38, 581566980, 748015 39, 542777973, 768340 40, 938256762, 789247 41, 404519574, 810834 42, 65078412, 817678 43, 2099436753, 824203 44, 834989157, 830982 45, 301557804, 838659 46, 2977815603, 846575 47, 1103763900, 854392 48, 458657868, 861899 49, 684977178, 869408 50, 747187692, 876678 51, 1620113013, 883805 52, 2546312292, 890814 53, 1562244489, 897842 54, 1098951666, 904583 55, 1135325334, 911203 56, 1507257945, 918257 57, 2697306330, 925121 58, 433197963, 932048 59, 2232922992, 938707 60, 98056845, 946894 61, 2271472254, 954196 62, 1337443800, 960897 63, 418254810, 967911 64, 2818012152, 974992 65, 1586419635, 981348 66, 2517201609, 987477 67, 1971790698, 993959 68, 485731278, 1000362 69, 2597065392, 1006659 70, 1631242632, 1012795 71, 1802120022, 1019112 72, 2084816757, 1025014 73, 2620109115, 1030915 74, 1452240594, 1036914 75, 455212932, 1043267 76, 28432782, 1049244 77, 828911184, 1055194 78, 1312790709, 1061164 79, 2643362361, 1067167 80, 2190684822, 1073078 81, 247496448, 1079044 82, 339706146, 1085133 83, 2586140088, 1091722 84, 1860951639, 1098217 85, 2232612519, 1104240 86, 1070121525, 1110342 87, 656770047, 1116570 88, 2094332778, 1122880 89, 226205853, 1129595 90, 886632087, 1135640 91, 2455346808, 1142169 92, 1582864266, 1148153 93, 689704227, 1154143 94, 867615654, 1160255 95, 108885105, 1166533 96, 1574475108, 1172690 97, 780179880, 1178743 98, 2060664024, 1185046 99, 2304125418, 1191493 100, 666623985, 1197723 101, 1753346802, 1203674 102, 2078562912, 1209904 103, 643869183, 1216013 104, 612764106, 1222037 105, 346287633, 1228075 106, 2619351147, 1234141 107, 746608884, 1240318 108, 1860549231, 1246315 109, 169787424, 1252563 110, 1878468873, 1258576 111, 809423367, 1264654 112, 1125905301, 1270643 113, 2907555195, 1276578 114, 1920529956, 1282612 115, 1733577633, 1288613 116, 349267383, 1294638 117, 1192989729, 1300699 118, 311338770, 1306699 119, 2291845452, 1312839 120, 1187486613, 1318770 121, 1676319297, 1324423 122, 217734270, 1330018 123, 1194337500, 1335658 124, 1044703368, 1341232 125, 566306103, 1346862 126, 856898760, 1352598 127, 2798895687, 1358327 128, 2563206678, 1363938 129, 752348622, 1369577 130, 1731759558, 1375200 131, 256361769, 1380821 132, 155183370, 1386405 133, 1753853880, 1392146 134, 1857030312, 1397745 135, 85062762, 1403397 136, 366056103, 1409023 137, 1761499767, 1414665 138, 2935202091, 1420318 139, 1122808359, 1425919 140, 941911593, 1431523 141, 2302885524, 1437249 142, 937056039, 1442872 143, 2862157134, 1448576 144, 1770354894, 1454173 145, 1850028105, 1459799 146, 2313073515, 1465419 147, 2532576891, 1471191 148, 846752541, 1476896 149, 278494332, 1482574 150, 2989614849, 1488241 151, 1036054062, 1495388 152, 1073981154, 1503503 153, 3056409891, 1512045 154, 1016612334, 1520215 155, 521547456, 1528717 156, 1070668095, 1536973 157, 792973002, 1545299 158, 2737162884, 1552788 159, 463386315, 1559478 160, 2438873799, 1566312 161, 2833554483, 1572827 162, 2175097242, 1579449 163, 487423905, 1586115 164, 390222945, 1592832 165, 1342304115, 1599574 166, 1273766244, 1606255 167, 1133510781, 1613010 168, 352243092, 1619868 169, 1167137184, 1626664 170, 2417600985, 1633506 171, 564158580, 1640250 172, 3074824362, 1647003 173, 172754091, 1653788 174, 2679412215, 1660546 175, 1117769772, 1667470 176, 2086592154, 1674185 177, 214729020, 1680789 178, 1284614826, 1687541 179, 2846124930, 1694228 180, 690166149, 1700656 181, 2951036067, 1707589 182, 691845264, 1714321 183, 1524318036, 1721050 184, 460889979, 1727770 185, 1565626146, 1734493 186, 2322372168, 1741153 187, 2787762450, 1747790 188, 2765183454, 1754481 189, 2413457022, 1761069 190, 1378605138, 1767786 191, 3030050334, 1774368 192, 2611143000, 1780814 193, 2587175196, 1787080 194, 1474227099, 1793308 195, 150756867, 1799602 196, 204824487, 1805864 197, 735977988, 1812113 198, 2157265173, 1818368 199, 2286000708, 1824565 200, 2911450221, 1830750 201, 438330000, 1836996 202, 2788173588, 1843230 203, 1595095032, 1849448 204, 2001615192, 1855693 205, 222973887, 1861899 206, 2434371969, 1868150 207, 2572064673, 1874320 208, 840797271, 1880347 209, 179763966, 1886441 210, 1984391454, 1892541 211, 1919911413, 1898944 212, 2285103918, 1904933 213, 359639547, 1911956 214, 1244664987, 1919429 215, 1892913297, 1927237 216, 2344980525, 1934778 217, 955051920, 1942249 218, 2337230418, 1949775 219, 1313511159, 1957124 220, 1609410498, 1963919 221, 480414126, 1970861 222, 1419895971, 1977656 223, 2057959983, 1984458 224, 149980539, 1991947 225, 322951866, 1999963 226, 279233094, 2007697 227, 1412240160, 2015181 228, 46676715, 2023129 229, 2339674371, 2031089 230, 2022475008, 2038794 231, 2563944168, 2046358 232, 2904722628, 2053451 233, 2432813718, 2060577 234, 2308290090, 2067559 235, 1359018999, 2074570 236, 1600942197, 2081418 237, 1147474350, 2088219 238, 1607996319, 2095495 239, 1892143941, 2102088 240, 303538266, 2108576 241, 2144836557, 2114961 242, 772838943, 2121300 243, 1680389685, 2127688 244, 3067555695, 2133985 245, 2267398095, 2140373 246, 2756736825, 2146737 247, 1224488073, 2153129 248, 1027660185, 2159462 249, 1460588133, 2165983 250, 2235886896, 2172438 251, 951576246, 2178735 252, 948783027, 2185913 253, 1924081578, 2192443 254, 2482773567, 2198929 255, 1812717225, 2205355 Last fiddled with by LaurV on 2022-08-10 at 14:34
 2022-08-18, 08:35 #6 Dieter   Oct 2017 139 Posts T(n) := time to compute the number of ways to perform a dance of n units. T(2^256) = 2^232 * T(2^24) ??? Are there algorithms without "T is proportional to n"? I only want to know, if there are such algos.
2022-08-18, 20:26   #7
uau

Jan 2017

5×31 Posts

Quote:
 Originally Posted by Dieter I only want to know, if there are such algos.
Pretty obviously there are unless you assume the bonus question is impossible (and it already has listed solvers) - would have to be an implausibly low constant of proportionality for it to be possible with work proportional to 2^256.

2022-08-24, 15:58   #8
KangJ

Jul 2015

1510 Posts

Quote:
 Originally Posted by dg211 The solver list got updated yesterday, so looks like I've just missed it and will have to wait for official verification of my solution. Can someone please tell me if these last three digits are correct? 399 for 2^24 499 for 2^256
I got the same answer as the number you wrote, and I'm pretty sure it's correct.

2022-08-24, 16:09   #9
KangJ

Jul 2015

3·5 Posts

Quote:
 Originally Posted by Dieter T(n) := time to compute the number of ways to perform a dance of n units. T(2^256) = 2^232 * T(2^24) ??? Are there algorithms without "T is proportional to n"? I only want to know, if there are such algos.

The time complexity can be O(log n).

So you can easily get the answer even for n = 2^100000.

(The number is 2703445608 for n = 2^100000, and only 12 seconds elapsed in my code.)

2022-08-26, 20:08   #10
SmartMersenne

Sep 2017

100100102 Posts

Quote:
 Originally Posted by KangJ The time complexity can be O(log n). So you can easily get the answer even for n = 2^100000. (The number is 2703445608 for n = 2^100000, and only 12 seconds elapsed in my code.)
I hope that you can show us how after the answer is published.

 2022-08-28, 05:48 #11 Dieter   Oct 2017 2138 Posts Meanwhile my best code needs 45 seconds for the transition from 2^n to 2^(n+1). One thread, I don´t know how to parallelize.

 Similar Threads Thread Thread Starter Forum Replies Last Post tgan Puzzles 3 2021-09-06 11:24 Xyzzy Puzzles 3 2020-08-29 08:33 Xyzzy Puzzles 20 2019-09-09 09:40 Xyzzy Puzzles 2 2014-11-02 19:04 Wacky NFSNET Discussion 0 2007-08-09 02:32

All times are UTC. The time now is 08:58.

Thu Feb 9 08:58:32 UTC 2023 up 175 days, 6:27, 1 user, load averages: 1.11, 0.91, 0.81