Mathematische Formel zum Generieren Incresing Sequenzen

Question

Ich habe zwei Lookup-Tabellen, die ich gerne mit einfachen Mathe entfernen würde, wenn möglich.

Die erste ist eine Abbildung von Indizes in einem Array zu der Sequenz {0} => 1, {1, 2} => 2, {3, 4, 5} => 3, s.t. es eine 1 zwei 2s, 3s drei usw. oder visuell:

lookup1[N] = { 
    1, 
    2, 2, 
    3, 3, 3, 
    4, 4, 4, 4, 
    5, 5, 5, 5, 5, 
    6, 6, 6, 6, 6, 6, 
    7, 7, 7, 7, 7, 7, 7, 
    8, 8, 8, 8, 8, 8, 8, 8, 
    ... 
} 

Die zweite zur Erhöhung Sequenzen ist, ist die erste Sequenz (1), die zweiten (1, 2), die dritte (1 , 2, 3). Es ist wie ein Moduluszyklus, aber steigt nach jedem Zyklus. Visuell:

lookup2[N] = { 
    1, 
    1, 2, 
    1, 2, 3, 
    1, 2, 3, 4, 
    1, 2, 3, 4, 5, 
    1, 2, 3, 4, 5, 6, 
    1, 2, 3, 4, 5, 6, 7, 
    1, 2, 3, 4, 5, 6, 7, 8, 
    1, 2, 3, 4, 5, 6, 7, 8, 9, 
    ... 
} 

Diese müssen aus Indizes zugeordnet werden. Für die zweite Suche würden die Eingänge 5, 4, 3 auf 3, 2 bzw. 1 abgebildet.

Gibt es mathematische Formeln, die diese Muster erzeugen würden? Ich würde lieber ein paar Anweisungen ausführen als einen Speicherzugriff.

Answer 1

Für lookup1 sieht das eng verwandt mit Triangular numbers, tatsächlich ist es das inverse Problem. Die Dreiecke sind die Anzahl der Elemente in einem Dreieck mit n Zeilen. Sie haben also T1 = 1, T2 = 1 + 2 = 3, T3 = 1 + 2 + 3 = 6, T4 = 1 + 2 + 3 + 4 = 10. Oder als Funktion f (1) = 1, f (2) = 3, f (3) = 6, f (4) = 10.

Sie wollen die inverse so tun, g (1) = 1, g (3) = 2, g (6) = 3, g (10) = 4. Wir sorgen uns später um andere Werte.

Es gibt eine Formel für die Dreieckszahl f (n) = n (n + 1)/2 und ein komplexeres eine für die inversen

g(n) = (sqrt(8 * n + 1) - 1)/2 

ein kleines Experiment zeigt, dass

ceil((sqrt(8*n+1) - 1)/2) 

gibt Ihre gewünschten Nummern.

Für den zweiten Teil können Sie die Funktion für die inverse Dreieckszahl verwenden und dann die vorherige Dreieckszahl finden, und nehmen Sie die Differenz

X = ceil((sqrt(8*n+1) - 1)/2); 
T = (X * (X-1))/2 ; 
print(n-T); 

Ein leichter warnender Hinweis. An den Übergangspunkten sollte sqrt(8*n+1) zu einem ungeraden ganzzahligen Wert ausgewertet werden. Was für sehr große n passieren könnte, ist, dass Rundungsfehler eine Rolle spielen könnten. Ich habe das auf über eine Million getestet und das Problem nicht auftreten gesehen.