Anzahl aller dezimalen Nachkommastellen einer mathematischen Konstante die benötigt werden, um alle n-stellige Zeichenketten (Zifferkombinationen) garantiert zu finden.
engl.: Number of digits in the decimal expansion of a constant that must be scanned to encounter all n-digit strings.
Konstante: A033307=Champernowne A000796=Pi=π  Näherung A001113 = e A002162=log(2) A002117=Zeta(3) A001622=phi
n A072290
 =10^n*(n-1/9)+n+10/9		 A036903 10^n*(1.7+2.15*n) A036904 A036905 A036906 ???????
1 11 32 39 21 22 23 23
2 192 606 600 372 444 457 770
3 2893 8555 8150 8092 7655 7839 5819
4 38894 99849 103000 102128 98370 83054 93910
5 488895 1369564 1245000 1061613 1107795 1256587 1154766
6 5888896 14118312 14600000 12108841 12983306 13881136 13192647
7 68888897 166100506 167500000 198150341   166670757  
8 788888898 1816743912 1890000000 1929504534      
9 8888888899 22445207406 21050000000        
10 98888888900 241641121048 232000000000        
11 1088888888901 2512258603207 2535000000000        
12 11888888888902   27500000000000        


Beispiel anhand der Zahlenfolge oeis.org/A254898, wo die Pi-Nachkommastellen rückwärts aufgelistet werden: 1, 41, 141, 5141, 95141,...
n spätestens bei Pos Fundposition  und Nachkommastellen
5 1369564     Pos=431047,      NK='47467787059514167095...
6 14118312        1365754,        '287688398129514106429...
7 166100506        3077948,       '3668469753629514164620...
8 1816743912      282604668,      '58330168815629514177722...
9 22445207406      369011020,     '846537633835629514196008...
10 241641121048     6304785793,    '2477768567535629514134457...
11 2512258603207    11934658784,   '82147903578535629514160777...
12 27500000000000  3286323248105,  '3983982097985356295141690... 
13 296500000000000  3286323248105,  '3983982097985356295141690... 
14 3180000000000000  3286323248105,  '3983982097985356295141690... 
  weitererFund 12917075598462,'449918619197985356295141656... 
15 33950000000000000 ?                                              
16 361000000000000000 ?                                              


Interessant: mathworld.wolfram.com/ConstantDigitScanning.html zeigt, dass Konstanten wie http://mathworld.wolfram.com/CatalansConstant.html durch BBP-type Summen analog zu Pi auch sehr ähnliche Folge (32, 716, 7700, 86482, 1143572,...) bilden analog zu A036903.

Bailey und Crandal zeigten im Jahr 2000 mit der oben erwähnten Bailey-Borwein-Plouffe-Formel, dass die Normalität von Pi zur Basis 2 auf eine Vermutung der Chaostheorie reduziert werden kann. 2012 gab's weitere Infos siehe LINK unten.

Die Copeland-Erdos Konstante A033308 {a[n]=a[n-1]+Prime(n).toString();a[0]="0.";} ist eine normale Zahl und ihre "Alle Zeichenketten Garantieposition" Folge 48, 934, 24437,366399,4910479, 49672582, ...
ist bisher immer größer als die von Pi. (eine Ziffernfolge ist in Pi schneller zu finden als in A033308)

Oder A001620 {Gamma=Euler-Mascheroni Const.}: 16, 658, 6600, 91101, 1384372,... {Muster "18" endet an Stelle 658 }

zurück zur Nachkommastellendatenbank
Muster in irrationalen Zahlen


LINKS (neben Wikipedia's Normale Zahl):
2012: http://www.davidhbailey.com/dhbpapers/normality.pdf
2006: www.math.tugraz.at/~aistleitner/Diplomarbeit_Aistleitner.pdf
2006: http://arxiv.org/abs/math.NT/0512404
2002: www.emis.de/journals/EM/expmath/volumes/11/11.4/pp527_546.pdf
2001: http://mathworld.wolfram.com/news/2001-10-04/normal/
http://mathworld.wolfram.com/NormalNumber.html
http://oeis.org/A036903


Geschwindigkeitsoptimierung von Ziffernsuch-Experimenten irrationaler Zahlen (Juli 2014)
a) Zunächst sollte der mathematische Such-Algorithmus optimiert werden. Da es hier jedoch um gigantisch große Datenmengen (7 HD mit über 8 TB)
Nachkommastellen irrationaler Zahlen {neben Pi noch über 1 Mio. andere} geht, kann man weder mit Indizierung noch mit Suchmustern arbeiten.
Wie man an der Zahlenfolge A036903 sieht, wird die letzte 11 stellige Ziffernkombination in Pi erst an der Stelle 2512258603207
(etwa 2,5 Bio.=2500 mal 1 GB) gefunden. Außerdem wird hier die Suche nicht abgebrochen (sobald 1 Suchstring gefunden), sondern
es werden immer alle Stellen durchsucht und man kann sich glücklich schätzen, wenn man 1 von 28 Suchstrings pro 100 GB gefunden hat.

b) Was gut funktioniert ist Parallelisierung mit Mehrkernprozessoren. Wenn die 1 GB erst mal im schnellen RAM sind, kann man bis zu
70 Suchstrings parallel suchen lassen -> ergibt bei 8 Kernen einen Geschwindigkeitsfaktor um 5 bis 6.

c) Nicht nur wegen der großen Datenmenge, sondern auch wegen der relativ langsamen Festplattendatentransferrate bieten sich 2 Arten der Komprimierung an:
§1: ZIP - schafft mit 7ZiP eine Verkleinerung auf 45% und lässt sich schnell auspacken.
§2: ycd - 19 Ziffern werden in Hexzahl mit 8 Byte gespeichert, womit man fast 42% schafft
(wegen der Überlappungsgrenze kann man jedoch nicht den Suchstring nach Hex wandeln und nur in den 42% suchen)

d) Optimierung der Suchfunktion: PureBasic hat sich als einfaches und schelles Compilertool hervorgetan.
- echter kurzer 64Bit Maschinencode
- schnelles Auspacken der großen ZIP Dateien
- *mem statt String konnte den Speicherverbrauch halbieren; die Geschwindigkeit (siehe http://www.purebasic.fr/german/viewtopic.php?f=3&t=28159)
von FindStringOptimierung1() und NicTheQuick sein findMemory() verbesserte sich pro 20s dabei nur um minimale 1 s
- richtig viel brachte die Optimierung per ASM: Helle hat mit SSE4.2 Befehlen neuer CPUs noch einmal eine Geschwindigkeitsfaktor bis zu 3,4 gebracht

e) weitere Optimierung bringt das parallele Suchen mehrerer EXE auf mehreren Festplatten

Praktische Messungen mit einem i7-3770K (8 Thread-Kerne):
A)SSD-HD 10 * 1GB = 10 GB gezippt
- TotalCommander 1 Suchstring (11 bis 16 Zeichen) = 176 s (12 bis 13% CPU Auslastung)
- Optimierung b) bis d) 28 Suchstrings gleichzeitig  56 s (100% CPU Auslastung)
Steigerung um Faktor 3,14 * 28 = 88 (8700 %) !!!
B) USB 3.0 5 * 2 GB = 10 GB gezippt
- TotalCommander 1 Suchstring (11 bis 16 Zeichen) = 174 s (je nach Cache auch mal 180s)
- Optimierung b) bis d) ohne SSE4.2 28 Suchstrings= 190 s (Faktor 25,6)
- Optimierung b) bis d) 28 Suchstrings gleichzeitig  57 s (Faktor 85,5 ≅ 8450 %)
Anmerkungen:
- TotalCommander kann zwar auch per RegEx gleichzeitig nach mehreren Suchmustern suchen, aber das wird dann extrem langsam.
- andere Programme wie PRGrep und "EF Find" sind auch nicht schneller als TotalCommander
- bei Daten bis zu 2 GB macht sich der HD-Cache (RAM Puffer-Speicher für einmal gelesene Dateien) natürlich positiv bemerkbar
-> daher Vergleichstests immer mit mindestens 10 GB


Software-Geschwindigkeitsvergleich (Benchmark) 3^x sehr große Zahlen (i7-3770K 3,5 GHz ; AMD FX 8320 3,5 GHz):


Schon jetzt nach 5 Optimierungen über 52000 mal schneller als Microsofts .NET Framework 4.5 BigInteger.Pow(3,int) c#:

Software-Geschwindigkeitsvergleich
- AMD FX 8320 3,5 GHz ist trotz gleicher Taktfrequenz und Kernzahl etwa 3 mal langsamer als der i7 wegen _mm_mul_pd (128 Bit Multiplikation) und Turbo-Boost
(*) je nach RAM- & Festplattengeschwindigkeit (da ab hier Auslagerung auf Festplatte nötig)
(1) Stand 01.07.2015: 3^16911433728 = 2.5809436749192852 e 8068804479 (fast 8 GB)
Approximation (Hochrechnung) 3^(805306368*2602)=3^2095407169536=3^(3^25.82418683648...)=3.915154..*10^999763297877 (1TB Platte) ergibt per Iterationsrechner je nach Festplattengeschwindigkeit beim i7 optimistisch 3,7 ... pessimistisch 4,3 Jahre.
Mit Karazuba 1 nochmals 15,5% schneller ab 3^17 Mrd. (was bei größeren Potenzen noch besser wird!)...
12.07.2015: Parallelisierung von Schreib- & Lese-Befehlen (zeitgleich zur Berechnung) 18,6 % statt 15,5%
Damit nähert man sich der 3 Jahres Grenze (1TB): Iterationsrechner
(2) Stand 31.07.2015: 3 Optimierungen weiter...

NextPrime-Benchmark unterschiedliche CPUs, 32 & 64 Bit, 1 bis 8 Kerne