Die Mathe-Redaktion - 28.05.2018 05:22 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 59 Gäste und 1 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Wauzi
Zahlentheorie » Teilbarkeit » größte Teiler der Form 2^n für 843314856! mit Pi-Weg beweisen?
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule größte Teiler der Form 2^n für 843314856! mit Pi-Weg beweisen?
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 425
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-04-18


Gegeben: unglaublich große Zahl 843314856! (7161172778 Dezimalstellen)

Gesucht: größter Teiler der Form 2^n oder kurz:
843314856! mod 2^n = 0; n= ganze positive Zahl; gesucht: maximales n

Natürlich kann man das bei kleinen Zahlen wie 100! leicht durchsuchen lassen:
table 100! mod (2^n),n=95...99
n  | 100! mod (2^n)
95 | 0
96 | 0
97 | 0
98 | 158456325028528675187087900672
99 | 158456325028528675187087900672

In einem Forum fand ich eine elegantere Form der Summation der abgeschnittenen Teiler:
table floor(100/2^k),k=1...floor(ln(100)/ln(2))
k | floor(100/2^k)
1 | 50
2 | 25
3 | 12
4 | 6
5 | 3
6 | 1

kurz: sum floor(100/2^k),k=1...floor(ln(100)/ln(2))
ergibt richtige 97

Diese Folge kommt mir aus Kreiszahl Pi 9. Zahlenfolgen bekannt vor.

Und so ist sum floor(Pi*2^k),k=-1...floor(ln(100)/ln(2)-2) auch 97.

Nach diesem Muster sollte Das Ergebnis einfach:
sum floor(843314856/2^k),k=1...floor(ln(843314856)/ln(2)) ergibt 843314841
oder
sum floor(Pi*2^k),k=-1...floor(ln(843314856)/ln(2)-2) ergibt auch  843314841
sein.

Habe gerade kein Mathematica zur Hand: ist
843314856! mod (2^843314841) wirklich 0 ?

Kann man beweisen, dass das immer so ist?



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4032
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-04-18


Das Ergebnis ist natürlich richtig, deine Art der Berechnung ist aber aus algorithmischer Sicht denkbar umständlich. Sie sollte so erfolgen, wie in nachfolgendem - und hoffentlich selbsterklärenden - Maple-Programm:
Maple
test:=proc(n)
   local r,s:=0,t:=2;
   do
      r:=floor(n/t); if r=0 then return s end if;
      t:=2*t; s:=s+r
   end do
end:
 
test(843314856)
                           843314841





  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 683
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2018-04-18


Hallo hyperG,

ich habe mal
Mathematica
Mod[843314856!, 2^843314841]
in Mathematica eingegeben - da kommt tatsächlich 0 heraus.

Des Weiteren:
Soweit ich sehe ist diese Formel
2018-04-18 19:22 - hyperG im Themenstart schreibt:
sum floor(843314856/2^k),k=1...floor(ln(843314856)/ln(2)) ergibt 843314841
offenbar richtig, während diese hier
2018-04-18 19:22 - hyperG im Themenstart schreibt:
sum floor(Pi*2^k),k=-1...floor(ln(843314856)/ln(2)-2) ergibt auch  843314841
nicht immer das richtige Resultat liefert (z. B. bei Argument 300 fälschlicherweise 398 statt 296 oder z. B. bei Argument 7000 fälschlicherweise 6428 statt 6993).

weird hat mal wieder einen sehr schnellen Algoritmus gefunden für das Problem. Die Funktion arbeitet korrekt soweit ich es überprüft habe, und ich hab sie mal nach Mathematica übersetzt:
Mathematica
Test[n_] := 
  Module[{r, s, t},
    s = 0; t = 2; 
    While[True,
      r = Floor[n/t];
      If[r == 0, Return[s]];
      t = 2*t; s = s + r
    ]
  ]
(* Aufruf *)
Test[843314856]

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 1487
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-04-19

\(\begingroup\)
Statt immer $\left \lfloor{\frac{n}{p^k}} \right \rfloor$ zu rechnen, ist es potentiell einfacher, $n_{k+1} = \left \lfloor {\frac{n_k}{p}} \right \rfloor$ zu berechnen.
C++
// max({k if p^k | N!})
int max_k(int N, int p){int k=0;while(N)k+=N/=p;return k;}
 
int main(int argc, char** argv) {
	printf("max k with 843314856! mod 2^k == 0: %d\n",max_k(843314856,2)); // => 843314841
	printf("max k with 843314856! mod 10^k == 0: %d\n",max_k(843314856,5)); // => 210828707
	return 0;
}
 



-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4032
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2018-04-19

\(\begingroup\)
2018-04-19 09:26 - DerEinfaeltige in Beitrag No. 3 schreibt:
Statt immer $\left \lfloor{\frac{n}{p^k}} \right \rfloor$ zu rechnen, ist es potentiell einfacher, $n_{k+1} = \left \lfloor {\frac{n_k}{p}} \right \rfloor$ zu berechnen.

Ja, das Bessere ist der Feind des Guten, wie man so schön sagt. Ist ja echt lustig, dass sowohl ich, als auch Primentus und schon gar hyperG diese einfache Möglichkeit übersehen haben.   biggrin

Maple
nu:=proc(n,p:=2)
   local n_:=n,s:=0;
   do
      n_:=floor(n_/p); if n_=0 then return s end if;
      s:=s+n_
   end do
end:
 
nu(843314856)
                           843314841
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 425
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2018-04-19


2018-04-18 21:20 - Primentus in Beitrag No. 2 schreibt:
...
nicht immer das richtige Resultat liefert (z. B. bei Argument 300 fälschlicherweise 398 statt 296 oder z. B. bei Argument 7000 fälschlicherweise 6428 statt 6993).

...


Genau das geht in die eigentliche Fragerichtung...
also nicht um die Optimierung des 1. Algorithmus, sondern die Verbindung zu Pi oder anderen irrationalen Zahlen beim 2. Algorithmus.

Das Argument muss natürlich in der Folge enthalten sein.
Bei Argument 300 enthält die Folge floor(Pi*2^k) {also A068425 }
keine 300. {sondern 100, 201, 402,...}
Tauscht man Pi durch reellen 75/32 oder irrationalen Faktor (40554*Pi)/54359 , funktioniert es:
Folgen mit Argument 300
sum floor(300/2^k),k=1...floor(ln(300)/ln(2)) ergibt 296
 
sum floor(75/32*2^k),k=-1...floor(ln(300)/ln(2)-2) ergibt 296
 
sum floor(40554*Pi/54359*2^k),k=-1...floor(ln(300)/ln(2)-2) ergibt 296

Bei 7000 analog das gleiche.

Die Frage, die ich besser hätte gleich stellen sollen, lautet:
wenn Algorithmus 1
f1(x)= sum floor(x/2^k),k=1...floor(ln(x)/ln(2))
ist dann bis in alle Ewigkeit
f2(x)= sum floor(Faktor*2^k),k=-1...floor(ln(x)/ln(2)-2)
identisch dazu, wenn floor(Faktor*2^k)=x mit k=floor(ln(x)/ln(2)-1)

Also kann der Faktor beliebig rational oder irrational sein?

Ich kann kaum glauben, dass eine abgeschnittene Divisionsfolge mit reellen Zahlen bis in alle Ewigkeit identische Folgeglieder bildet,
wie eine abgeschnittene Multiplikationsfolge mit irrationalen Zahlen.

Mir ist auch klar, dass 1/2^k = 1*2^(-k) , aber Index vom 2. Algorithmus ist nur um 2 verschoben und nicht negiert.

Das muss was mit den Binär-Bitstellen zu tun haben, aber das Abschneiden mit floor macht es kompliziert für Beweise.

Und wenn man die Differenzen zum Argument betrachtet, kommt man zu A000120
explizite Funktion
f3(x)=x-A000120(x)
f3(x)=x-hammingweight(x) {Pari / GP }

Das wäre dann Algorithmus 3. Wirklich alle identisch ?

Unter Wiki mehr...



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 425
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2018-04-19


Mal etwas größere Argumente:
Algorithmus 1
f1(143482587720256841293275162491978472764192344513)
sum floor(x/2^k),k=1...floor(ln(143482587720256841293275162491978472764192344513)/ln(2))=156
sum floor(143482587720256841293275162491978472764192344513/2^k),k=1...156
=143482587720256841293275162491978472764192344450 in unter 1s
Algorithmus 2
f2(143482587720256841293275162491978472764192344513)
sum floor(Pi*2^k),k=-1...154
=143482587720256841293275162491978472764192344450 in unter 1s
Algorithmus 3
f3(143482587720256841293275162491978472764192344513)
=143482587720256841293275162491978472764192344513-hammingweight(143482587720256841293275162491978472764192344513)
=143482587720256841293275162491978472764192344450 in ms per Pari


"Faszinierend!" würde Mr.Spock sagen.

Da selbst 200stellige Argumente unter 1 s Ergebnisse liefern, muss man oberhalb 600stellig vergleichen...



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 683
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2018-04-19


2018-04-19 14:51 - hyperG in Beitrag No. 5 schreibt:
Das Argument muss natürlich in der Folge enthalten sein.
Bei Argument 300 enthält die Folge floor(Pi*2^k) {also A068425 }
keine 300. {sondern 100, 201, 402,...}

Hallo hyperG,

ach so, ja - wenn man nur gültige Argumente in die Formel einspeist, dann stimmt sie natürlich.

2018-04-19 14:51 - hyperG in Beitrag No. 5 schreibt:
Tauscht man Pi durch reellen 75/32 oder irrationalen Faktor (40554*Pi)/54359 , funktioniert es:
Folgen mit Argument 300
sum floor(300/2^k),k=1...floor(ln(300)/ln(2)) ergibt 296
 
sum floor(75/32*2^k),k=-1...floor(ln(300)/ln(2)-2) ergibt 296
 
sum floor(40554*Pi/54359*2^k),k=-1...floor(ln(300)/ln(2)-2) ergibt 296

Bei 7000 analog das gleiche.

Ich kann es zwar nicht beweisen, aber ich persönlich glaube schon, dass es für eigentlich nicht gültige Argumente dann immer einen solchen rationalen oder irrationalen Faktor gibt, so dass das richtige Ergebnis herauskommt.

Habe es jedenfalls mal für die Argumente 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000 (Edit: nun auch für 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000, 100000) überprüft, und da konnte ich zu allen ein passendes Zähler/Nenner-Paar finden (sowohl in der Variante ohne als auch mit zusätzlichem Faktor Pi). Es würde mich ehrlich gesagt eher wundern, wenn das bei größeren Zahlen irgendwann nicht mehr der Fall sein sollte.

Durch das zweimalige Floor-Setzen ergeben sich sogar zahlreiche Möglichkeiten, ein Zähler/Nenner-Paar festzulegen, z. B. bei Argument 300 schon 14 Möglichkeiten, wenn Zähler und Nenner jeweils zwischen 1 und 100 sein sollen in der Variante ohne Pi, und sogar 34 Möglichkeiten in der Variante mit Pi bei gleichen Wertebereichen für Zähler und Nenner. Erweitert man die beiden Wertebereiche, gibt es noch viel mehr Lösungsmöglichkeiten. Insofern würde es mich doch sehr wundern, wenn die Anzahl Möglichkeiten der Zähler/Nenner-Festlegung irgendwann gegen Null ginge.

Übrigens ist es bei Argument 300 so, dass nicht 75/32 das erstmögliche Zähler/Nenner-Paar ist bei der Variante ohne Pi, sondern auch 33/14 ist schon eine Lösung, und bei der Variante mit Pi ist 3/4 schon die erstmögliche Lösung.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 425
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2018-04-19


Hallo Primentus,

unter Mathematica lautet hammingweight(x) vermutlich DigitCount[x, 2, 1]:

der 3. Algorithmus scheint auch mit WolframAlpha zu funktionieren:

f3(x)=x-DigitCount[x, 2, 1]

Damit berechnet man blitz schnell
11^1777-DigitCount[11^1777, 2, 1] aus!

{stimmt mit Pari GP überein}

unglaublich, was (11^1777)! für eine gewaltige Zahl mit
über 6.6..*10^1853 Stellen ist!!! (mehr Stellen als Atome im Weltall
oder über 10^1773 Ziffern für jedes Atom im Weltall !!!)

Bei Pi-Nachkommastellen (oder anderen irrationalen Zahlen, denn 10^1773 ist kein Glied der Pi*2^k Folge) wird Algorithmus 2 da kompliziert!



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 683
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2018-04-19


2018-04-19 18:30 - hyperG in Beitrag No. 8 schreibt:
unter Mathematica lautet hammingweight(x) vermutlich DigitCount[x, 2, 1]:

der 3. Algorithmus scheint auch mit WolframAlpha zu funktionieren:

f3(x)=x-DigitCount[x, 2, 1]

Hallo hyperG,

ja, es scheint tatsächlich so zu sein, dass sich hammingweight(x) in Mathematica als DigitCount[x, 2, 1] ausdrücken lässt. Ich habe es anhand zahlreicher Aufrufbeispiele überprüft und konnte nichts gegenteiliges feststellen. Das ist offensichtlich das, was Du mit Zusammenhang zum Binärsystem meintest - sehr interessant an dieser Stelle! Damit lassen sich, wenn man es von x abzieht, die gleichen Ergebnisse erzielen wie bei Deinen beiden anderen Algorithmen.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 425
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2018-04-19


Und man braucht das eigentliche Argument (wenn es in Formelschreibweise vorliegt) nicht ausrechnen, sondern hat gleich das Ergebnis in komprimierter Formelschreibweise vorliegen:

f3(1777^991777) = 1777^991777 - DigitCount[1777^991777, 2, 1]
=1777^991777-5353052

die 3222966 Stellen (!) könnte ich hier nicht so einfach hochladen.

Der Teiler hat damit die Form 2^(1777^991777-5353052).
Mehr als 10^3222964 Dezimalstellen -> nicht mehr vorstellbar.




  Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3075
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2018-04-19


Hallo.

Sei für eine Primzahl p und eine natürliche Zahl n

<math>v_p(n):=\text{Exponent von p in der Primfaktorenzerlegung von n!}</math>.

Dann gilt <math>\displaystyle v_p(n)=\frac {n-\text{Quersumme von n in der p-adischen Darstellung}}{p-1}</math>

Dieses Resultat erhält man ,wenn man in die Legendre Formel die p-adische Darstellung für n einsetzt,die beiden Summen vertauscht , die geometrische Summenformel anwendet und alles vereinfacht.

Die "Formel" ist äußerst effizient,da man nur noch Ganzzahlarithmetik benutzt.

Ich bin auf sie gestossen ,ohne sie vorher zu kennen  ,in diesem Thread:

<math>\frac {125-1}{5-1} = 31</math>.

Man kann mit ihr sehr schnell die Primfaktorenzerlegung von n! berechnen.

Man siehe hier.

Gruß endy



-----------------
Peter Scholze Fields Medal 2018 :
Sometimes I have some vague intuitive idea on how things should work, and I try to reconcile this with the known theory. In some cases the new perspective leads to new insights(CMI 2012).



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 683
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2018-04-19


2018-04-19 20:49 - hyperG in Beitrag No. 10 schreibt:
Und man braucht das eigentliche Argument (wenn es in Formelschreibweise vorliegt) nicht ausrechnen, sondern hat gleich das Ergebnis in komprimierter Formelschreibweise vorliegen:

Ja, das ist auf jeden Fall sehr praktisch.

2018-04-19 21:01 - endy in Beitrag No. 11 schreibt:
Sei für eine Primzahl p und eine natürliche Zahl n

<math>v_p(n):=\text{Exponent von p in der Primfaktorenzerlegung von n!}</math>.

Dann gilt <math>\displaystyle v_p(n)=\frac {n-\text{Quersumme von n in der p-adischen Darstellung}}{p-1}</math>

[...]

Die "Formel" ist äußerst effizient,da man nur noch Ganzzahlarithmetik benutzt.

Hallo endy,

die Formel ist wirklich sehr gut. Habe gerade mal Dein Mathematica-Notebook ausprobiert. Die Berechnungszeit ist wirklich sehr schnell - bei n=100000 sogar nur 0,11 Sekunden gegenüber fast 561 Sekunden bei Verwendung der Standardfunktion FactorInteger.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4032
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2018-04-19


2018-04-19 22:31 - Primentus in Beitrag No. 12 schreibt:
Hallo endy,

die Formel ist wirklich sehr gut. Habe gerade mal Dein Mathematica-Notebook ausprobiert. Die Berechnungszeit ist wirklich sehr schnell - bei n=100000 sogar nur 0,11 Sekunden gegenüber fast 561 Sekunden bei Verwendung der Standardfunktion FactorInteger.

Nur interessehalber und falls es für dich nicht zuviel Aufwand ist:  Was wäre denn vergleichsweise die Rechenzeit, wenn man meine Routine in #4 - codiert in Mathematica - für dieses Beispiel ausführt?



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 683
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2018-04-19


2018-04-19 23:01 - weird in Beitrag No. 13 schreibt:
Nur interessehalber und falls es für dich nicht zuviel Aufwand ist:  Was wäre denn vergleichsweise die Rechenzeit, wenn man meine Routine in #4 - codiert in Mathematica - für dieses Beispiel ausführt?

Hallo weird,

oh - sogar noch schneller!
Deine Funktion nu in Mathematica codiert
Mathematica
Nu[n_, p_: 2] := 
  Module[{nn, s},
    nn = n; s = 0; 
    While[True,
      nn = Floor[nn/p];
      If[nn == 0, Return[s]];
      s = s + nn
    ]
  ]
Timing[Nu[100000]]
liefert für n=100000 das Ergebnis 99994 in 0 Sekunden (das bedeutet in Mathematica üblicherweise, dass die Berechnungszeit kleiner als 0,015 Sekunden ist).

Erst ab
Mathematica
Timing[Nu[10^12]]
kommt erstmals eine Berechnungszeit von knapp über 0,015 Sekunden zustande (0,015625).

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4032
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2018-04-20


@Primentus

Alles andere als diese Traumzeit hätte mich jetzt auch höchst erstaunt. Danke wieder einmal!  wink



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 425
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, vom Themenstarter, eingetragen 2018-04-20


Hallo endy,

ja, diese universellere Formel für beliebige Primfaktoren
- stimmt bei Primfaktor=2 mit meiner f3(x) exakt überein
- ist besonders für Primfaktor=5 interessant, da man die Nullen am Ende damit bestimmen kann

Ich habe sie mit dem Rekursiven Algorithmus vom
Iterationsrechner Beispiel 56 verglichen.
Alle Werte stimmten.
Statt 1 DigitCount sind es dann 4, da der Befehl
Total(IntegerDigits(n,5)) per WolframAlpha nicht funktionierte (beide einzeln funktionierten komischerweise?).

Dieses Bit-Zählen ist extrem schnell und erlaubt - wie schon zuvor beschrieben - das Rechnen mit Zahlen, die in keinen PC hineinpassen, da sie mehr Stellen also Atome im Weltall haben.

@Primentus

zu "...sogar noch schneller!"
Schneller als was genau?

Zuvor sprichst Du von endy's Mathematica-Code und dem Befehl FactorInteger -> diese suchen doch ALLE FAKTOREN (bei 100000! sind es über 9000).
Die kann man doch nicht mit dem 1 besonders einfachen Fall Faktor=2 vergleichen.
Spätestens, wenn der 1. Parameter Deiner Nu(n_ ... Funktion überläuft,
wirst Du merken, welcher gewaltige Geschwindigkeitsvorteil von 1 Befehl DigitCount gegenüber einer Schleife von zig Divisionen steckt.

Oder der Code von der factorIntegerFactorial.nb
ist schlecht umgesetzt, was ich aber ohne Mathematica nicht nachvollziehen kann.

Wenn Nu(10^12) 0,015625 s dauert,
sollte Nu(10^16) über 200 s dauern (nichtlinearer Ansieg).

10^16- DigitCount[10^16, 2, 1]=9999999999999980 in unter 1 s



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4032
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2018-04-20

\(\begingroup\)
2018-04-20 14:14 - hyperG in Beitrag No. 16 schreibt:
Wenn Nu(10^12) 0,015625 s dauert,
sollte Nu(10^16) über 200 s dauern (nichtlinearer Ansieg).

10^16- DigitCount[10^16, 2, 1]=9999999999999980 in unter 1 s

Deine obigen Überlegungen bezüglich des Anstiegs der Rechenzeit kann ich in keiner Weise nachvollziehen. Um größere Werte rechnen zu können, ohne dass der Bildschirm "geflutet" wird, habe ich mal die Intialisierung der Variablen $s$ in #4 auf $s:=-n$ abgeändert habe, womit also dann die Abweichung von $n$ ausgegeben wird. Diese sollte also dann bis auf das Vorzeichen genau mit deinem DigitCount[n,2,1] übereinstimmen.

Maple
nu:=proc(n,p:=2)
   local n_:=n,s:=-n;
   do
      n_:=floor(n_/p); if n_=0 then return s end if;
      s:=s+n_
   end do
end:
 
t:=time():nu(10^16),(time()-t)*'s'
                            -20, 0.
 
t:=time():nu(10^100000),(time()-t)*'s'
                       -115979, 52.531 s

Für $n=10^{16}$ kann ich dir leider mit keiner Rechenzeit dienen, da diese auf meinem PC "unter der Wahrnehmungsgrenze" liegt, für $n=10^{100000}$ dauert das Ganze schon  etwas länger, aber sie liegt immer noch unter 1 min.

Damit hätten wir also dann eine wirklich gute Vergleichsmöglichkeit. Aber wie lange auch immer dein DigitCount[n,2,1] für diesen Wert von $n$ auch braucht, du wirst merken, dass für diese Rechnung doch intern eine ganze Menge an Rechenoperationen ablaufen, sodass der Aufruf dieser Funktion also alles andere als "gratis" ist, wie du offenbar zu glauben scheinst.   biggrin
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 683
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2018-04-20

\(\begingroup\)
@weird:

Gern geschehen!

2018-04-20 14:14 - hyperG in Beitrag No. 16 schreibt:
da der Befehl
Total(IntegerDigits(n,5)) per WolframAlpha nicht funktionierte (beide einzeln funktionierten komischerweise?)

Hallo hyperG,

ja, WolframAlpha hat in der kostenlosen Variante einige Einschränkungen - man kann in der Regel keine Verschachtelungen von mehreren Funktionen aufrufen, auch keine längeren Funktionsparameter angeben und auch keine selbst definierten Funktionen aufrufen. Hinsichtlich dieser Dinge soll man eben dazu animiert werden, sich das kostenpflichtige Mathematica zuzulegen. wink

2018-04-20 14:14 - hyperG in Beitrag No. 16 schreibt:
zu "...sogar noch schneller!"
Schneller als was genau?

Schneller als endy's Funktion factorIntegerFactorial[n] meinte ich.

2018-04-20 14:14 - hyperG in Beitrag No. 16 schreibt:
Zuvor sprichst Du von endy's Mathematica-Code und dem Befehl FactorInteger -> diese suchen doch ALLE FAKTOREN (bei 100000! sind es über 9000).
Die kann man doch nicht mit dem 1 besonders einfachen Fall Faktor=2 vergleichen.

Ja, ok, der Vergleich mit der Mathematica-Standard-Funktion FactorInteger[n!] mag vielleicht etwas hinken, aber trotzdem muss man ja erstmal draufkommen, dass es noch alternative Berechnungsmöglichkeiten gibt.

2018-04-20 14:14 - hyperG in Beitrag No. 16 schreibt:
Wenn Nu(10^12) 0,015625 s dauert,
sollte Nu(10^16) über 200 s dauern (nichtlinearer Ansieg).

10^16- DigitCount[10^16, 2, 1]=9999999999999980 in unter 1 s

Also ich hab jetzt nochmal einen Vergleich von Nu[n] und n-DigitCount[n, 2, 1] mit Mathematica durchgeführt. Dabei zeigt sich, dass Nu[n] erstmals ab ca. $n=10^{27400}$ die "Schallmauer" von 1 Sekunde Berechnungszeit durchbricht, wohingegen n - DigitCount[n, 2, 1] für selbiges $n$ erstaunlicherweise immer noch unter 0,015 Sekunden Berechnungszeit liegt. endy's factorIntegerFactorial[n] hingegen erreicht bereits erstmals ab ca. $n=1500000$ die "Schallmauer" von 1 Sekunde.

Wenn Du es also so haben willst, ergibt sich folgendes Geschwindigkeitsranking:
1. n - DigitCount[n, 2, 1] von hyperG
2. Nu[n] von weird
3. facotorIntegerFactorial[n] von endy

LG Primentus

[Die Antwort wurde nach Beitrag No.16 begonnen.]
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 683
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2018-04-20


Hallo weird,

ich glaube, ich habe herausgefunden, wie man
Mathematica
n - DigitCount[n, 2, 1]
in Maple ausdrücken kann:
Maple
n - numboccur(convert(n, binary), 1)
Für die beiden n einfach den entsprechenden Wert einsetzen.
Versuch das mal. Möglicherweise ist die Berechnungszeit in Maple da auch sehr schnell - schauen wir mal. wink

LG Primentus




  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4032
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2018-04-20

\(\begingroup\)
2018-04-20 17:24 - Primentus in Beitrag No. 19 schreibt:
Möglicherweise ist die Berechnungszeit in Maple da auch sehr schnell - schauen wir mal. wink

Ja, du hast die Maple-Syntax dafür fast erraten, aber dann doch nicht ganz.  wink

Tatsächlich lautet die entsprechende Routine

Maple
t:=time():numboccur(convert(10^100000, base,2), 1),(time()-t)*'s'
                        115979, 0.125 s
 

und sie ist wirklich extrem schnell, was mich jetzt schon ein bißchen überrascht. *) Dem steht aus didaktischer Sicht allerdings der Nachteil gegenüber, dass  es sich dabei letztlich um eine "Blackbox" handelt, auch wenn die "Idee" dahinter natürlich klar ist.

*) Möglicherweise spielt da auch der "Zufall" ein gewisse Rolle, dass der Computer intern ohnehin mit der Binärdarstellung der Zahlen rechnet, d.h., für Primzahlen $p>2$ sollte es dann zwar noch immer schnell, aber doch nicht mehr ganz so flott gehen.
 
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 683
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2018-04-20


Hallo weird,

ups - "base, 2" statt "binary" - da hab ich mich wohl vertan. wink
Danke für die Richtigstellung!

Ja, ich finde es ehrlich gesagt auch sehr erstaunlich, dass das selbst bei so gigantisch großen Zahlen noch so rasend schnell geht. Allerdings - ja - leider kann man nicht in diese Standardfunktionen hineinschauen, wie sie genau arbeiten.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4032
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, eingetragen 2018-04-20

\(\begingroup\)
2018-04-20 18:38 - Primentus in Beitrag No. 21 schreibt:
ups - "base, 2" statt "binary" - da hab ich mich wohl vertan. wink
Danke für die Richtigstellung!

Um genau zu sein gibt es beide Möglichkeiten, welche sich nur in der Ausgabe - nämlich als ganze Zahl mit Ziffern in $\{0,1\}$, oder als Liste von 0'en und 1'en - unterscheiden. Nur die zweite ist aber mit numboccur kombinierbar.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 683
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, eingetragen 2018-04-20

\(\begingroup\)
2018-04-20 18:59 - weird in Beitrag No. 22 schreibt:
2018-04-20 18:38 - Primentus in Beitrag No. 21 schreibt:
ups - "base, 2" statt "binary" - da hab ich mich wohl vertan. wink
Danke für die Richtigstellung!

Um genau zu sein gibt es beide Möglichkeiten, welche sich nur in der Ausgabe - nämlich als ganze Zahl mit Ziffern in $\{0,1\}$, oder als Liste von 0'en und 1'en - unterscheiden. Nur die zweite ist aber mit numboccur kombinierbar.

Ach so, verstehe. Dann braucht man in dem Fall sozusagen die Listenform.

LG Primentus
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3075
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, eingetragen 2018-04-22


Hallo.

Ich nenne

legendre1 die Funktion test aus Beitrag Nr.2. Quasi Legendre naiv

legendre2 die Funktion Nu aus Beitrag Nr.14. Quasi Legendre mit Rekurrenz

legendre3 wie in Beitrag Nr.11 beschrieben und ein kleiner Teil von factorintegerfactorial aus dem verlinkten Notebook.Quasi Legendre in p-adischer Darstellung.

Hier ist die Berechnung des Problems aus dem Titel mit den 3 Funktionen:
mathematica
(* In *)
Clear @ "Global`*"
hyperq = 843314856
legendre1[n_] := Module[{r, s, t}, s = 0; t = 2;
  While[True, r = Floor[n/t];
   If[r == 0, Return[s]];
   t = 2*t; s = s + r]]
legendre2[n_, p_: 2] := Module[{nn, s}, nn = n; s = 0;
  While[True, nn = Floor[nn/p];
   If[nn == 0, Return[s]];
   s = s + nn]]
legendre3[n_, p_] := (n - (IntegerDigits[n, p] // Total))/(p - 1)
 
legendre1[hyperq] // Timing
legendre2[hyperq] // Timing
legendre3[hyperq, 2] // Timing
 
(* Out *)
 
843314856
{0., 843314841}
{0., 843314841}
{0., 843314841}

Die Ergebnisse stimmen also überein und alle 3 Algorithmen sind gleich schnell bzw. die Laufzeit ist so klein,dass man keine Unterschiede bemerkt.

Jetzt ein größeres Argument zum testen:
mathematica
(* In *)
n = 10^15000;
legendre1 @n == legendre2 @ n
legendre1 @n == legendre3 [n, 2]
 
legendre1[n]; // Timing // First
legendre2[n] ; // Timing // First
legendre3[n, 2]; // Timing // First
 
(* Out *)
 
True
True
 
5.662836
0.436803
0.

Die Ergebnisse stimmen also überein.Die Laufzeiten sind aber sehr unterschiedlich.

endy




  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 683
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, eingetragen 2018-04-22


Hallo endy,

ach ja, mir wird jetzt erst so richtig bewusst, dass die Funktion factorIntegerFactorial[n] aus Deinem Mathematica-Notebook ja alle Primfaktoren ermittelt, was naturgemäß natürlich länger dauert. Für einen fairen Vergleich mit den Funktionen von hyperG und weird genügt es natürlich, lediglich den Exponenten des Primfaktors 2 zu ermitteln, wie Du es jetzt mit der Funktion legendre3[n, p] formuliert hast. Diese Funktion ist tatsächlich ähnlich schnell wie die DigitCount-Variante, die hyperG vorgeschlagen hatte.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 394
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.26, eingetragen 2018-04-24


Hab auch mal ein kleines Programm erstellt.
Zum Bsp.
Ergibt wohl:

Fakultät: (10^19)!
Basis b, sodas (10^19)! MOD b^n=0 für b= 41:
n=249999999999999995




  Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3075
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.27, eingetragen 2018-04-24


@ Nr.26 :

Dies ist korrekt.

Nachgerechnet mit den 3 etwas verbesserten Legendre Funktionen aus Beitrag Nr.24 :
mathematica
(* In *)
Clear @ "Global`*"
 
legendre1[n_, p_: 2] := Module[{r, s = 0, t = p},
  While[True, r = Floor[n/t];
   If[r == 0, Return[s]];
   t = p*t; s = s + r]]
legendre2[n_, p_: 2] := Module[{nn = n, s = 0},
  While[True, nn = Floor[nn/p];
   If[nn == 0, Return[s]];
   s = s + nn]]
legendre3[n_, p_: 2] := (n - (IntegerDigits[n, p] // Total))/(p - 1)
 
legendre1[10^19, 41] // Timing
legendre2[10^19, 41] // Timing
legendre3[10^19, 41] // Timing
 
(* Out *)
 
{0., 249999999999999995}
{0., 249999999999999995}
{0., 249999999999999995}
 

endy



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4032
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.28, eingetragen 2018-04-24

\(\begingroup\)
@endy

Hm, vielleicht irre ich mich ja, aber ich glaube nicht, dass deine Routinen in #27 gegenüber denen in #24 noch in jedem Fall korrekt funktionieren. Wenn nämlich im Hauptprogramm z.B. s vor dem Aufruf der beiden ersten Unterroutinen einen Wert ungleich 0 bekommt, dann wird meines Wissens nach die Initialisierung $s=0$ in dem Modul, welche ja auch auf jeden Fall noch vorher erfolgt, dann mit diesem neuen Wert von $s$ überschrieben. Bei der tatsächlichen Ausführung von Unterroutinen in Mathematica werden ja dann Initialisierungen von lokalen Variablen nicht mehr berücksichtigt, sondern meines Wissens nach einfach übersprungen.

Vielleicht kann ja auch Primentus, der sich genau mit diesem Problem auch schon herumgeschlagen hat, bevor wir es dann gemeinsam lösen konnten, auch noch etwas dazu sagen.  wink
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 394
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.29, eingetragen 2018-04-24


Da bin ich beruhigt.
Ich sehe, das das Verfahren mit dem von mir erdachten übereinstimmt.

Code:
 DIM AS UINTEGER F,B,Count
 Count=0
 INPUT "Fakultät";F
 INPUT "Basis";B
 
 WHILE F>=B
 Count+=F\B
 F=F\B
 WEND
 
 PRINT COUNT:SLEEP



  Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3075
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.30, eingetragen 2018-04-24

\(\begingroup\)
@weird Nr.28:

Du meinst also,dass s keinen Wert ungleich 0 haben darf, bevor man die Routinen legendre1 und legendre2 aufruft ?
mathematica
(* In *)
 
Clear @ "Global`*"
legendre1[n_, p_: 2] := Module[{r, s = 0, t = p},
  While[True, r = Floor[n/t];
   If[r == 0, Return[s]];
   t = p*t; s = s + r]]
legendre2[n_, p_: 2] := Module[{nn = n, s = 0},
  While[True, nn = Floor[nn/p];
   If[nn == 0, Return[s]];
   s = s + nn]]
 
s = 12;
legendre1[10^19, 41] // Timing
legendre2[10^19, 41] // Timing
 
(* Out *)
{0., 249999999999999995}
{0., 249999999999999995}
 

Es funktioniert also alles wunderbar.

Zur Erläuterung :
mathematica
Clear @ "Global`*"
 
(* In *)
m = 127
test:= Module[{m = 0}, m]
test
m
 
(* Out*)
 
127
0
127
 

Wie wird test berechnet? Folgendermaßen:
mathematica
(* In *)
m = 127
test := Module[{m = 0}, m]
Trace @test //ColumnForm
m
 
(* Out *)
 
127
ColumnForm[{
HoldForm[test], 
HoldForm[
Module[{m = 0}, m]], {
HoldForm[m$10366 = 0], 
HoldForm[0]}, {
HoldForm[m$10366], 
HoldForm[0]}, 
HoldForm[0]}]
127
 

Mathematica generiert also durch Module zu einer lokalen Variable mit den Namen name eine Variable mit dem Namen name$number , wobei number bei jedem Modulaufruf nach oben gezählt wird.

Dies ist genau dasselbe Prinzip wie der Mathematicabefehl Unique wirkt:
http://reference.wolfram.com/language/ref/Unique.html.

Wo ist das Problem bei Primentus aufgetreten?

Gruß endy



\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 683
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.31, eingetragen 2018-04-25


Hallo,

sorry, dass ich mich jetzt erst melde, aber habe eben erst vor kurzem gelesen, was ihr geschrieben habt.

@endy @weird:

Soweit ich sehe, arbeiten Deine Funktionen richtig, endy.
Ich denke es geht um das Missverständnis, dass weird darauf hinaus wollte, dass es bei ineinander geschachtelten selbst geschriebenen Mathematica-Funktionen, welche lokale Variablen gleichen Namens verwenden, zu unerwünschten Überlagerungen von Variablenwerten kommen kann. Um dies zu vermeiden, darf man meines Erachtens die anfänglichen Variableninitialisierungen innerhalb eines Moduls erst NACH dem anfänglichen {}-Block platzieren (Bekanntgabe der Variable innerhalb von {}, aber die Initialisierung erst danach). Da Deine Funktionen legendre1, legendre2 und legendre3 sich aber nicht gegenseitig aufrufen, endy, d. h. nicht ineinandergeschachtelt sind, sondern unabhängig voneinander arbeiten, tritt hier das von weird vermutete Problem nicht auf.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 425
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.32, vom Themenstarter, eingetragen 2018-04-25


2018-04-24 16:55 - pzktupel in Beitrag No. 29 schreibt:
Da bin ich beruhigt.
Ich sehe, das das Verfahren mit dem von mir erdachten übereinstimmt.

Code:
 DIM AS UINTEGER F,B,Count
 Count=0
 INPUT "Fakultät";F
 INPUT "Basis";B
 WHILE F>=B
 Count+=F\B
 F=F\B
 WEND
...

Hallo Norman,

ich sehe keinen Unterschied zum Algorithmus aus Beitrag No.3,
also nur ein Dialekt-Unterschied von c++ & BASIC.

Außerdem ist das schon fast die 64-Bit-Grenze.

Spätestens bei F=1777^991777 (was ja mit UINTEGER nicht funktioniert)
erkennt man den gewaltigen Vorteil der DigitCount-Algorithmen.



Mich interessiert auch wie weird, wie diese "Blackbox" Funktionen
genau funktionieren. Zur Basis 2 ist ja noch recht einfach und mit Sprachen wie Pari/GP & Maple nachvollziehbar.

Bei höheren Basen wie 41 ist es erstaunlich, wie schnell Wolfram's
IntegerDigits[1777^991, 41]
also eine 3221stellige Zahl nach Basis 41 gewandelt und daraus die Bits gezählt hat -> da gibt's bestimmt Abkürzungen...
(wie bei PowPowMod Funktionen).

Bei IntegerDigits[1777^991777, 41]
bleibt dann selbst WolframAlpha stehen :-)


Die eigentliche Frage aus Beitrag 5 (und der Überschrift), ob Algorithmus 2 mit jedem Faktor funktioniert, ist immer noch offen.
Es reicht auch ein Gegenbeweis: gibt es einen Faktor aus
floor(Faktor*2^k)=x mit k=floor(ln(x)/ln(2)-1)
wo
f2(x)= sum floor(Faktor*2^k),k=-1...floor(ln(x)/ln(2)-2)
ein anderes Ergebnis als die restlichen Algorithmen f1(x), f3(x),..
liefert?


Grüße



  Profil  Quote  Link auf diesen Beitrag Link
Horst_h
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 22.08.2017
Mitteilungen: 53
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.33, eingetragen 2018-04-26


Hallo,



Bei höheren Basen wie 41 ist es erstaunlich, wie schnell Wolfram's
IntegerDigits[1777^991, 41]
also eine 3221stellige Zahl nach Basis 41 gewandelt und daraus die Bits gezählt hat -> da gibt's bestimmt Abkürzungen...
(wie bei PowPowMod Funktionen).

IntegerDigits wandelt die Zahl zur Basis, da werden keine Bits oder Digits gezählt.
DigitCount[1777^991, 41] müsste eine Liste der Anzahl der Vorkommen von 0..40 ausgeben.
reference.wolfram.com/language/ref/DigitCount.html
In[1]:=         DigitCount[100!]
Out[1]=        {15,19,10,10,14,19,7,14,20,30}

DigitCount zur Basis 2 ,1 ist ja einfach ein popCount Befehl, der Zahl in interner Darstellung, also extrem schnell.

Vielleicht kann man ja
en.wikipedia.org/wiki/Superparticular_ratio Wallis- oder Euler Produkt nutzen ala
n! / Annäherung( pi/2 ) = ??

Gruß Horst




  Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3075
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.34, eingetragen 2018-04-27


Hallo.

Ich habe einmal die Funktion IntegerDigits aus Beitrag Nr.32 selbst in mma programmiert:
mathematica
(* In *)
 
Clear @ "Global`*"
 
integerdigits[number_, base_: 10] := 
 Module[{numbervar = number, a, j, 
   length = Floor[Log[number]/Log[base] // N]},
  For[j = length, j >= 0, j--, a[j] = Floor[numbervar/base^j]; 
   numbervar = numbervar - a[j] base^j];
  a /@ Range [0, length] // Reverse]
 
number = 11111111111111111111114444444445555
base = 177
 
integerdigits[number]
sol1 = integerdigits[number, base]
sol2 = IntegerDigits[number, base]
sol1 == sol2
 
IntegerDigits[1777^991, 1141] == 
  integerdigits[1777^991, 1141] // AbsoluteTiming
 
integerdigits[1777^9917, 41]; // AbsoluteTiming
IntegerDigits[1777^9917, 41]; // AbsoluteTiming
 
IntegerDigits[1777^99177, 41]; // AbsoluteTiming
IntegerDigits[1777^991777, 41]; // AbsoluteTiming
 
(* Out *)
 
11111111111111111111114444444445555
177
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, \
4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5}
{2, 21, 15, 63, 147, 143, 76, 141, 51, 33, 5, 28, 43, 98, 86, 75}
{2, 21, 15, 63, 147, 143, 76, 141, 51, 33, 5, 28, 43, 98, 86, 75}
True
{0.148008, True}
{76.059350, Null}
{0.003000, Null}
{0.059003, Null}
{1.067061, Null}
 

Positiv ist also,dass die Funktion integerdigits wohl korrekt arbeitet.Aber ihre Performance ist zu der in mma implementierten Funktion IntegerDigits sehr schlecht.

Wie geht es besser ?

endy



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 425
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.35, vom Themenstarter, eingetragen 2018-04-28


Mich fasziniert der Geschwindigkeitsvorteil von DigitCount gegenüber IntegerDigits bei Basen kleiner 11 (hier mal die interessante Basis 5):
WolframAlpha
DigitCount[1777^991, 5, 4]*4+DigitCount[1777^991, 5, 3]*3+DigitCount[1777^991, 5, 2]*2+DigitCount[1777^991, 5, 1]
ergibt in 1 s 9217

während
WolframAlpha
IntegerDigits(1777^991 ,5)
{nachträgliches Total[] funktioniert leider nur mit Mathematica oder kleineren Arrays }
erst nach etwa 20 s Ergebnisse liefert (nachträgliche Addition ergibt auch 9217)

Schon bei IntegerDigits(1777^9917 ,5) gibt's keine Antwort mehr,
ABER
WolframAlpha
DigitCount[1777^9917, 5, 4]*4+DigitCount[1777^9917, 5, 3]*3+DigitCount[1777^9917, 5, 2]*2+DigitCount[1777^9917, 5, 1]
liefert schon nach 1 s 92105

selbst
WolframAlpha
DigitCount[1777^99177, 5, 4]*4+DigitCount[1777^99177, 5, 3]*3+DigitCount[1777^99177, 5, 2]*2+DigitCount[1777^99177, 5, 1]
liefert in weniger als 2 s 921237.
Da muss es eine Abkürzung geben!

Und bei derart gigantischen Zahlengrößen funktioniert auch keine Näherung oder log(...) wäre zu ungenau...



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 425
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.36, vom Themenstarter, eingetragen 2018-04-28

Wolfram Alpha
DigitCount[9777^99177, 5, 4]*4+DigitCount[9777^99177, 5, 3]*3+DigitCount[9777^99177, 5, 2]*2+DigitCount[9777^99177, 5, 1]
=1129925 in weniger als 2 Sekunden!
d.h. (9777^99177)! hat bei Basis 5 den größten Exponent
Wolfram Alpha
(9777^99177-1129925)/(5-1)=1.0477005990713058101432738117752653077368810261751... × 10^395736
Das ist die Anzahl der Nullen am Ende dieser hyper-gigantischen Fakultätszahl.
Pro Atom unseres Weltalls {man schätzt etwa 10^80 im gesamten Weltall} kämen mehr als 10^395656 Nullen!!!!

DigitCount kann unmöglich in so kurzer Zeit so eine große Zahl in Basis 5 wandeln.

Könnte es denn eine Zahl geben, wo garantiert keine Abkürzung funktioniert wie:
Fibonacci(1.5e6)=1.290892168118740*10^313481 also minimal kleiner als 9777^99177:
Wolfram Alpha
DigitCount[Fibonacci(1.5e6), 5, 4]*4+DigitCount[Fibonacci(1.5e6), 5, 3]*3+DigitCount[Fibonacci(1.5e6), 5, 2]*2+DigitCount[Fibonacci(1.5e6), 5, 1]
liefert in etwa 5 s den winzigen Wert 44 ????
Kann das jemand mit Mathematica bestätigen?
Ist dieser Wert nicht viel zu klein?????? Ergänzung: FEHLER bei WolframAlpha -> siehe weiter unten!

IntegerDigits(Fibonacci(1.5e6), 5) liefert wie erwartet kein Ergebnis,
da man so große Zahlen in so kurzer Zeit nicht in andere Basen wandelt.

Andere Sprache:
Pari/GP
vecsum(digits(fibonacci(1500000),5)) 
= 898084 in weniger als 1 s

OK, geht doch schnell!
Pari/GP
vecsum(digits(9777^99177,5))=1129925 weniger als 1 s

stimmt also mit DigitCount überein!

Sogar vecsum(digits(9777^991777,5)) funktioniert in etwa 2 s !!!!!!
Mächtig gewaltig!



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 683
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.37, eingetragen 2018-04-28


2018-04-28 11:17 - hyperG in Beitrag No. 36 schreibt:
Wolfram Alpha
DigitCount[Fibonacci(1.5e6), 5, 4]*4+DigitCount[Fibonacci(1.5e6), 5, 3]*3+DigitCount[Fibonacci(1.5e6), 5, 2]*2+DigitCount[Fibonacci(1.5e6), 5, 1]
liefert in etwa 5 s den winzigen Wert 44 ????
Kann das jemand mit Mathematica bestätigen?

Hallo hyperG,

ja, ich kann bestätigen, dass bei mir in Mathematica auch der Wert 44 herauskommt.

2018-04-28 11:17 - hyperG in Beitrag No. 36 schreibt:
IntegerDigits(Fibonacci(1.5e6), 5) liefert wie erwartet kein Ergebnis,
da man so große Zahlen in so kurzer Zeit nicht in andere Basen wandelt.

Man kann schon die IntegerDigits einer so großen Zahl ermitteln. Wenn die Ausgabe zu lange dauert (und das Ergebnis ist hier ja eine Liste), liegt das eher daran, dass Mathematica Probleme damit hat, solch große Listen im Notebook auszugeben, da das bei mehreren hunderttausend Einträgen offenbar große Ressouren erfordert. Man kann aber z. B. alternativ die Länge der Liste abfragen, sprich die Anzahl Stellen dieser großen Fibonacci-Zahl:
Mathematica
Timing[Length[IntegerDigits[Fibonacci[1500000], 5]]]
(* Ausgabe *)
{0.078125, 448491}
Und das geht dann in rasanten 0,078 Sekunden, wie man sieht. Intern werden die einzelnen digits aber auf jeden Fall ermittelt. Zum Beispiel könnte man die Ziffern Nr. 1000 bis 1005 dieser Zahl ausgeben, was ebenfalls sehr schnell geht:
Mathematica
Timing[Take[IntegerDigits[Fibonacci[1500000], 5], {1000, 1005}]]
(* Ausgabe *)
{0.09375, {4, 0, 0, 4, 4, 2}}

Die IntegerDigits in eine Datei umzuleiten müsste eigentlich auch halbwegs schnell gehen, was ich jetzt aber nicht ausprobiert habe. Nur bei der direkten Ausgabe solch langer Listen direkt im Mathematica-Notebook kann es schon mal geraume Zeit dauern, weil hierfür ja wirklich explizit jede Ziffer ermittelt und dargestellt werden muss.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 425
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.38, vom Themenstarter, eingetragen 2018-04-28


Hallo Primentus,

bitte nicht Length[IntegerDigits[Fibonacci[1500000], 5]]
sondern Total[IntegerDigits[Fibonacci[1500000], 5]]
da wir ja hier nicht die Länge, sondern die Summe der Ziffern haben wollen -> da müsste dann auch 898084 herauskommen.

ABER warum funktioniert
DigitCount[9777^99177, 5, 4]*4+DigitCount[9777^99177, 5, 3]*3+DigitCount[9777^99177, 5, 2]*2+DigitCount[9777^99177, 5, 1]
während
DigitCount[Fibonacci(1.5e6), 5, 4]*4+DigitCount[Fibonacci(1.5e6), 5, 3]*3+DigitCount[Fibonacci(1.5e6), 5, 2]*2+DigitCount[Fibonacci(1.5e6), 5, 1]
so einen winzigen Wert liefert?

Ich hab's: Wolfram rundet intern, wenn Eingabe hinter dem Punkt nur wenige Ziffern folgen!

DigitCount[Fibonacci(1500000), 5, 4]*4+DigitCount[Fibonacci(1500000), 5, 3]*3+DigitCount[Fibonacci(1500000), 5, 2]*2+DigitCount[Fibonacci(1500000), 5, 1] =898084 stimmt dann!

Beispiel 366836 ist in Basis 5 =43214321
a) Total[IntegerDigits[366836, 5]] = 20
b) vecsum(digits(366836,5)) =20
c) DigitCount[366836, 5, 4]*4+DigitCount[366836, 5, 3]*3+DigitCount[366836, 5, 2]*2+DigitCount[366836, 5, 1]=20
denn die 4 taucht 2 mal auf mit der Wertigkeit 4, die 3 zweimal mit Werigkeit 3 usw. -> da stimmt noch alles


ABER bei DigitCount[Fibonacci(1.5e6), 5, 4] kommt eine 2 heraus!!
Die Ziffer 4 ist doch in dieser gewaltigen Zahl in Basis 5 nicht nur 2 mal vorhanden!


Beweis:
Fibonacci(1.5e6) mod 1000000000000000000 liefert bei WolframAlpha eine 0
Ausgeschrieben jedoch:
Fibonacci(1500000) mod 1000000000000000000 liefert 956168354898000000
wie auch
www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php
Fibonacci(1500000,,,N=1000000000000000000 )  = 956168354898000000




  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 683
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.39, eingetragen 2018-04-28


2018-04-28 17:54 - hyperG in Beitrag No. 38 schreibt:
bitte nicht Length[IntegerDigits[Fibonacci[1500000], 5]]
sondern Total[IntegerDigits[Fibonacci[1500000], 5]]
da wir ja hier nicht die Länge, sondern die Summe der Ziffern haben wollen -> da müsste dann auch 898084 herauskommen.

Hallo hyperG,

ja, stimmt - da kommt dann 898084 heraus.

2018-04-28 17:54 - hyperG in Beitrag No. 38 schreibt:
ABER warum funktioniert
DigitCount[9777^99177, 5, 4]*4+DigitCount[9777^99177, 5, 3]*3+DigitCount[9777^99177, 5, 2]*2+DigitCount[9777^99177, 5, 1]
während
DigitCount[Fibonacci(1.5e6), 5, 4]*4+DigitCount[Fibonacci(1.5e6), 5, 3]*3+DigitCount[Fibonacci(1.5e6), 5, 2]*2+DigitCount[Fibonacci(1.5e6), 5, 1]
so einen winzigen Wert liefert?

Ich hab's: Wolfram rundet intern, wenn Eingabe hinter dem Punkt nur wenige Ziffern folgen!

Ok, ich muss dazu sagen, dass ich bei dem Fall, wo 44 herauskam, 1.5*10^6 eingegeben hatte. Wenn man es als 1500000 eingibt, kommt tatsächlich das richtige heraus. Ich hätte jetzt aber nicht gedacht, dass diese beiden Arten der Eingabe einen Unterschied machen.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
hyperG hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]