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

 2018-12-10, 22:46 #1 Teonum   Feb 2018 1 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 134628 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 6016 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     Oct 2020 Spain-UE 3 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

Oct 2020
Spain-UE

3 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

3×2,963 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 613 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 36810 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     Oct 2020 Spain-UE 316 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.

 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:55.

Sun Nov 29 17:55:15 UTC 2020 up 80 days, 15:06, 4 users, load averages: 1.13, 1.73, 1.81

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.