August 2022

tgan · 2022-08-02, 09:55

https://research.ibm.com/haifa/ponde...ugust2022.html

dg211 · 2022-08-09, 19:52

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

LaurV · 2022-08-10, 02:14

Is this question asked after submitting, or before submitting? Can you prove?

dg211 · 2022-08-10, 08:47

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

LaurV · 2022-08-10, 14:34

Haha, it was a joke man, as the tongued smiley at the end says... You don't need to prove anything to us.

Your post sounded like you already sent the solution, but after the list was published (read it again!) and you missed being on the list. But the list was already 3 days older (4 now), as the last result is from 6, so I was just half curious if you already sent the solution, as it seemed, and want us to confirm to make your waiting easier, or you didn't send it yet and wanted us to ensure you that the solution is right, so you know if you should send it or not.

There is a big difference between the two. While the first is human, the second looks a bit like cheating. Assuming the numbers don't fit, will you ask us to confirm different and different numbers again and again, until they match?

In fact, I can not certify your numbers, because I did not solve the puzzle and I don't know how to solve it, because I didn't have the patience to read it more than superficially. Too long, too busy. What I can do, is to mask your numbers in your post, to make sure you don't spoil it to other people. I don't know if should I just mask it or delete it. I will go with the mask this time.

Dieter · 2022-08-18, 08:35

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.

uau · 2022-08-18, 20:26

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.

KangJ · 2022-08-24, 15:58

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.

KangJ · 2022-08-24, 16:09

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.)

SmartMersenne · 2022-08-26, 20:08

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.

Dieter · 2022-08-28, 05:48

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.

2022-08-02, 09:55	#1
tgan Jul 2015 2×19 Posts	August 2022 https://research.ibm.com/haifa/ponde...ugust2022.html Last fiddled with by tgan on 2022-08-02 at 09:57

2022-08-10, 08:47	#4
dg211 Jun 2016 11100₂ 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-10, 14:34	#5
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2829₁₆ Posts	Haha, it was a joke man, as the tongued smiley at the end says... You don't need to prove anything to us. Your post sounded like you already sent the solution, but after the list was published (read it again!) and you missed being on the list. But the list was already 3 days older (4 now), as the last result is from 6, so I was just half curious if you already sent the solution, as it seemed, and want us to confirm to make your waiting easier, or you didn't send it yet and wanted us to ensure you that the solution is right, so you know if you should send it or not. There is a big difference between the two. While the first is human, the second looks a bit like cheating. Assuming the numbers don't fit, will you ask us to confirm different and different numbers again and again, until they match? In fact, I can not certify your numbers, because I did not solve the puzzle and I don't know how to solve it, because I didn't have the patience to read it more than superficially. Too long, too busy. What I can do, is to mask your numbers in your post, to make sure you don't spoil it to other people. I don't know if should I just mask it or delete it. I will go with the mask this time. Last fiddled with by LaurV on 2022-08-10 at 14:37

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

2022-08-09, 19:52	#2
dg211 Jun 2016 2²×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-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-28, 05:48	#11
Dieter Oct 2017 213₈ 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.