Computing Dedekind number D(9).

Teonum · 2018-12-10, 22:46

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.

CRGreathouse · 2018-12-11, 03:39

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.

JM Montolio A · 2018-12-11, 15:22

" 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

JMARANDA · 2020-10-07, 13:10

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.

JMARANDA · 2020-10-07, 19:15

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

Comments

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.

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

Uncwilly · 2020-10-07, 19:39

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.

Stargate38 · 2020-10-12, 22:41

@JMARANDA: Your GitHub link is giving me a 404. Any chance you could fix that?

kruoli · 2020-10-13, 08:21

It's http://github.com/JOSMAN-UE/Dedekind-M8-51-minutes., including the dot in the end.

JMARANDA · 2020-10-15, 16:45

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.

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)= 2F(14)=284 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, 15:22	#3
JM Montolio A Feb 2018 96₁₀ 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)= 2F(14)=284 D(8)=F(256)= 2F(240). F(2^e+1)=2F(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 2S(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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
GPU Computing newbie	lukerichards	GPU Computing	10	2019-04-10 02:10
History of Computing	Nick	Computer Science & Computational Number Theory	0	2017-10-10 20:45
GPU Computing Cheat Sheet (a.k.a. GPU Computing Guide)	Brain	GPU Computing	20	2015-10-25 18:39
Could a Distributed Computing approach help find the smallest Brier number?	jasong	Math	5	2007-05-29 13:30
The difference between P2P and distributed computing and grid computing	GP2	Lounge	2	2003-12-03 14:13

2018-12-11, 03:39	#2
CRGreathouse Aug 2006 3·1,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.

2020-10-12, 22:41	#7
Stargate38 "Daniel Jackson" May 2011 14285714285714285714 7²·13 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 197₁₆ 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 3 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.