mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2022-08-02, 09:55   #1
tgan
 
Jul 2015

37 Posts
Default August 2022

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

Last fiddled with by tgan on 2022-08-02 at 09:57
tgan is offline   Reply With Quote
Old 2022-08-09, 19:52   #2
dg211
 
Jun 2016

308 Posts
Default

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
dg211 is offline   Reply With Quote
Old 2022-08-10, 02:14   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

2·47·109 Posts
Default

Is this question asked after submitting, or before submitting? Can you prove?
LaurV is offline   Reply With Quote
Old 2022-08-10, 08:47   #4
dg211
 
Jun 2016

23×3 Posts
Default

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
dg211 is offline   Reply With Quote
Old 2022-08-10, 14:34   #5
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

101000000001102 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2022-08-18, 08:35   #6
Dieter
 
Oct 2017

13310 Posts
Default

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.
Dieter is offline   Reply With Quote
Old 2022-08-18, 20:26   #7
uau
 
Jan 2017

23·19 Posts
Default

Quote:
Originally Posted by Dieter View Post
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.
uau is offline   Reply With Quote
Old 2022-08-24, 15:58   #8
KangJ
 
Jul 2015

168 Posts
Default

Quote:
Originally Posted by dg211 View Post
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 is offline   Reply With Quote
Old 2022-08-24, 16:09   #9
KangJ
 
Jul 2015

2·7 Posts
Default

Quote:
Originally Posted by Dieter View Post
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.)
KangJ is offline   Reply With Quote
Old 2022-08-26, 20:08   #10
SmartMersenne
 
Sep 2017

13910 Posts
Default

Quote:
Originally Posted by KangJ View Post
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.
SmartMersenne is offline   Reply With Quote
Old 2022-08-28, 05:48   #11
Dieter
 
Oct 2017

7·19 Posts
Default

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.
Dieter is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 19:03.


Mon Dec 5 19:03:19 UTC 2022 up 109 days, 16:31, 0 users, load averages: 1.11, 1.30, 1.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔