mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2018-12-10, 22:46   #1
Teonum
 
Feb 2018

1 Posts
Smile 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.
Teonum is offline   Reply With Quote
Old 2018-12-11, 03:39   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

134628 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2018-12-11, 15:22   #3
JM Montolio A
 
Feb 2018

6016 Posts
Thumbs up 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
JM Montolio A is offline   Reply With Quote
Old 2020-10-07, 13:10   #4
JMARANDA
 
JMARANDA's Avatar
 
Oct 2020
Spain-UE

3 Posts
Question 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.
JMARANDA is offline   Reply With Quote
Old 2020-10-07, 19:15   #5
JMARANDA
 
JMARANDA's Avatar
 
Oct 2020
Spain-UE

3 Posts
Oh, A132581...

Quote:
Originally Posted by CRGreathouse View Post
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.

----------------------------------------------------------------------------------------------------
JMARANDA is offline   Reply With Quote
Old 2020-10-07, 19:39   #6
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

3×2,963 Posts
Default

Quote:
Originally Posted by JMARANDA View Post
--------------------------------------------------------
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.
Uncwilly is offline   Reply With Quote
Old 2020-10-12, 22:41   #7
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

613 Posts
Default

@JMARANDA: Your GitHub link is giving me a 404. Any chance you could fix that?
Stargate38 is online now   Reply With Quote
Old 2020-10-13, 08:21   #8
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

36810 Posts
Default

It's http://github.com/JOSMAN-UE/Dedekind-M8-51-minutes., including the dot in the end.
kruoli is offline   Reply With Quote
Old 2020-10-15, 16:45   #9
JMARANDA
 
JMARANDA's Avatar
 
Oct 2020
Spain-UE

316 Posts
Default

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

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.