mersenneforum.org Computing Dedekind number D(9).
 Register FAQ Search Today's Posts Mark Forums Read

 2018-12-10, 22:46 #1 Teonum   8,219 Posts Computing Dedekind number D(9). 10-Dec-2018 Unpublished work, but privated registered. Hello, world. Im computing Dedekind numbers. Using a desktop i computed D(7). But i find many lines of research. I tell you what i find, here. - I extended the function to n. F(n): 2,(3) ,5, (6), 11,14,19, (20), 39... Sloane A132581. - Algorithms to evaluate F(n) and get the set C(n). - full or sequential chained. - F(for 2 powers, the Dedekind numbers). - using the published methods, someones extended. - many new methods: using rules over sets, trees, graphs or patterns. - evaluate: F(kn) from C(n). - get set C(kn) from C(n). - a compressed form for sets C(n), using symbol "X" as (0 and 1). Cardinality of set is few times less than F(). With good tree-like sizes. I developped the related 3-valued tables to operate with x-compressed sets. Example. C(4), Dedekind set n 2, is: 0000 0XX1 1111 A card 6, on 3 elements. C(6), 14 on 6. D(5), F(32), 7581 on 1200. - I find properties of F(n) that enables computing shortcuts to D. numbers. Examples. D(4)=F( 16)= 2*F(14)=2*84 D(8)=F(256)= 2*F(240). D(8) evaluation: (x2)C(120), (x3)C(80), (x4)C(60). - Properties of Differences(n) ¿ is a way to explicit expression? SLOANE. A132582. - using 3-value logic, i find: F(n,3) = F(2n,2) D(7)=F(128,2)=F(64,3). - F(n fixed,s) give a polynomial n graded on s. I call them Pol. of Dedekind. Table F(n,s). 1. 1,2,3,... 2. 1,3,6,10,.. 3. 1,5,14,30,55,91,140,.. 4. 1,6,20,50,105,.. 6. 1,14,84,330,1001,.. 8. 1,20,168,.. Questions. - whats new, whats old. - whats seams useful, whats not. - Ways to try to find explicit form for F(n). - One alg. to reduce C(n) to minimum cardinality. - ¿someone computing D(9)? Please, comment.
 2018-12-11, 03:39 #2 CRGreathouse     Aug 2006 5,987 Posts TL;DR: The OP is trying to compute D(9) with D(n) = A000372(n) = F(2^n) = A132581(2^n). See the sequences for background and references. Given the growth of the sequence (each term seems to be about the square of the previous term) I expect the computation to be pretty intense. I'd love to see calculation ideas.
 2018-12-11, 15:22 #3 JM Montolio A   Feb 2018 5×19 Posts What means TL , DR, OP ? " I'd love to see calculation ideas" Well, Im computing D(n) for last 4 months. Today best options i have are x-compressed sets and computing shorcuts. I find many others interesting ways but i cant explore them. Time. JMMA Note: I get some forum account problems. I post last work version. Title . Comments on some properties of Dedekind numbers. 11-Dec-2018. JMMA. Work private registered. Im computing Dedekind numbers. Using a desktop i computed D(7). And i find many lines of research. - I extended the function to n. F(n): 2,(3),5,(6),11,14,19,(20) ,39..84..(168)..2008..(7581).. Sloane A132581. - Algorithms to evaluate F(n) and get set C(n). - full or sequential-chained. - F(for 2 powers): the Dedekind numbers. - using the published methods, someones extended. - OR using new methods: rules over sets, trees, graphs or patterns. - rule based from condition (a LE b). - evaluate: F(kn) from C(n). - get set C(kn) from C(n). Example. D(8)=(x2)C(120)= (x3)C(80)= (x4)C(60). - a compressed form for sets C(n), using symbol "X" as (0 and 1). Cardinality of set is few times less than F(). With good tree-like sizes. I developped the related 3-valued tables to operate with x-compressed sets. Examples. Set C(4), Dedekind set n 2, is: 0000 0XX1 1111 A card 6, on 3 elements. Set C(6) 0000XX 0010X1 01001X 011011 0XX111 111111 Card 14, on 6. D(5)= F(32)= 7581, C(32) on 1200. Table (a LE b) for x-compressed sets. - 0 1 X 0 0 1 2 1 0 1 1 X 1 2 3 ------- Similar tables to get C(2n). - I find some properties of F(n). F(2^e)= F(2^e - 2^d) + F( ((2^d-1)/2^d)*(2^e)) D(4)=F( 16)= 2*F(14)=2*84 D(8)=F(256)= 2*F(240). F(2^e+1)=2*F(2^e-1)+1 F(2^e-2)=F(2^e-3)+F(2^(e-1)-1) F(2^e+2)=F(2^e)+F(2^e-1)+F(2^e-2) I used the properties to test computed values. And for computing D.numbers. - Differences(n), Dif(n). SLOANE A132582. Dif(n)=F(n)-F(n-1). Dif(n) LT F(n-1) Dif(n) as graph, or rule. At some n values, Dif(n) EQ F(m). n=(2^a-1)*(2^b), m=(2^(a-1)-1)*(2^e) n=(2^a+1)*(2^b), m=(2^a-1)*(2^e) - using 3-value logic (0,1,2) i find: F(n)=F(n,2). F(2n,2) = F(n,3). D(7)=F(128,2)=F(64,3). - F(n fixed,s) give a polynomial n graded on s. I call them Pol. of Dedekind. Table F(n,s from 1 to ). 1. 1,2,3,... 2. 1,3,6,10,.. 3. 1,5,14,30,55,91,140,.. 4. 1,6,20,50,105,.. 6. 1,14,84,330,1001,.. 8. 1,20,168,.. First Dedekind polynomials: D1(x)=x D2(x)=(x)(x+1)/2 D3(x)=(x)(x+1)(2x+1)/6 D4(x)=(x-1)(x)(x)(x+1)/12 A general expression is a open-question. - Dedekind numbers as subserie of F(n), are computed on many ways. These methods, changing some parameters, gives a full set of series Dedekind-like. Fibo is one of them. - Another open-question. All series with S(n) GT S(n-1); S(n) LE 2*S(n-1); Are Dedekind-like ??? 11Dic2018. JMMA
 2020-10-07, 13:10 #4 JMARANDA     "Account archived." Oct 2020 UE 31 Posts right place for Dedekind numbers? Someone interested on the Dedekind numbers problem? I computed M8 after 51' of Intel i3. I write a fast program. But computing serie A132581 is hard. I need bizarre computer power. Something like a Xeon 24Cores. Source is on github.
2020-10-07, 19:15   #5
JMARANDA

"Account archived."
Oct 2020
UE

31 Posts
Oh, A132581...

Quote:
 Originally Posted by CRGreathouse TL;DR: The OP is trying to compute D(9) with D(n) = A000372(n) = F(2^n) = A132581(2^n). See the sequences for background and references. I'd love to see calculation ideas.

--------------------------------------------------------
Sequence OEIS A132581.
"New values and one relationship."
ONLY "with n multiple of 4"

--------------------------------------------------------

New value obtained:* Discovered
n F(n) Relationship
---- ----------------------------- --------------------
128 0002.4146.8204.0998; M7.
160 0001.0915.5249.3226.6679; Last known.

164* 0005.8783.4149.5816.1884;
168* 0014.1975.3406.9172.3630;
172* 0039.3953.4418.5632.4853;
176* 0051.2617.1120.4101.3308;
180* 0161.5425.7144.5831.0110;
184* 0225.4830.5719.5672.0898;
188* 0332.3658.7553.6968.2762;
192* 0337.9107.8507.6574.6508; F192+F252=F256.
196* 1925.8137.5568.0675.8426;
200* 5238.7009.8371.8298.2255;
204* 0001.6780.3451.1261.6143.1395;
224* 0022.8147.0929.0804.6885.3455; F224+F248=F256.
240* 0280.6521.8614.3437.7895.3894; 2*F240=F256.
248* 0538.4896.6299.6070.8905.4333; See 224.
252* 0561.2705.8120.8367.9216.1280; See 192.
253* 0561.3043.7223.8582.0165.4146;
254* 0561.3043.7226.2728.7586.6790; F256=F254+F128.
255* 0561.3043.7228.6875.5790.7787; F255+1=F256.
---
256 0561.3043.7228.6875.5790.7788; M8.
---------------------------------------------------------

All calculated with the x64-86 OpenMP Windows10 EXE.
Released on: https://github.com/JOSMAN-UE/DEDEKIND-NUMBERS

The program can calculate each F(n) until M8,
with n multiple of 4, n between 8 and 256.

Time spent is not O(n). Some numbers require computer power.
Status. Pending: 208;212,216; 220,228; 232,236,244.

----------------------------------------------------------------------------------------------------

2020-10-07, 19:39   #6
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

10,799 Posts

Quote:
 Originally Posted by JMARANDA -------------------------------------------------------- Sequence OEIS A132581. "New values and one relationship." ONLY "with n multiple of 4"
Your crossposting in a new thread has been merged into this one. Please look for an existing thread before making a new one.

 2020-10-12, 22:41 #7 Stargate38     "Daniel Jackson" May 2011 14285714285714285714 2E316 Posts @JMARANDA: Your GitHub link is giving me a 404. Any chance you could fix that?
 2020-10-13, 08:21 #8 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 23×53 Posts It's http://github.com/JOSMAN-UE/Dedekind-M8-51-minutes., including the dot in the end.
 2020-10-15, 16:45 #9 JMARANDA     "Account archived." Oct 2020 UE 31 Posts Thanks for getting interested. A cordial greeting. JMMA. https://github.com/JOSMAN-UE. https://github.com/JOSMAN-UE https://github.com/JOSMAN-UE/A132582-Combinatory. https://github.com/JOSMAN-UE/Dedekind-M8-51-minutes. m8 has a set approach. e.c. a combinatorial approach. Some points are missing on the d7-d8 road. Even m8 requires in some cases quite computing power. The set approach is limited by memory. The combinatory is slower, but lacks limits. It works by calculating OEIS A132582 from every n. Several can be calculated in parallel. But it doesn't parallelize the individual calculation. In C the word limit is __int128, in C++ there is no word limit. In theory one could launch e.exe and reach d9. I'm updating github. If I get a parallel e.c. I'll put it on. Best regards. Well The Dedekind d9 is an unspotained peak. I encourage you to calculate it. There's nothing GIMPS can't do.
 2021-03-18, 00:07 #10 JMARANDA     "Account archived." Oct 2020 UE 3110 Posts D(9) is really hard. After D(8) , or F(256), few values of F() are known. I find some of these new values, like i post here time ago. I fail contact OEIS. Computing D(8) today requires some kind of fast Xeon cluster. And 4 hours time. I write one really more fastest program merging anything what i find and my best ideas. I post them on Github. It outperforms the previous program many times. Zero downloads, no forks. I contact previous team, at Nederlands: not more interested. Oh cruel world, give me one Cray and i move the D(9) !!
2021-03-18, 01:09   #11
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by JMARANDA I fail contact OEIS.
I'm not sure exactly what you were trying to do, but feel free to drop me a PM. I'm an Editor-in-Chief (and Trustee) at the OEIS. I don't know that there's anything useful we can do for you but I'd be happy to try.

 Similar Threads Thread Thread Starter Forum Replies Last Post lukerichards GPU Computing 10 2019-04-10 02:10 Nick Computer Science & Computational Number Theory 0 2017-10-10 20:45 Brain GPU Computing 20 2015-10-25 18:39 jasong Math 5 2007-05-29 13:30 GP2 Lounge 2 2003-12-03 14:13

All times are UTC. The time now is 17:44.

Tue Nov 29 17:44:54 UTC 2022 up 103 days, 15:13, 0 users, load averages: 0.98, 0.90, 0.92