Bist du schon verloren?

31

Ihre Aufgabe ist es, die Ganzzahlfolge A130826 zu implementieren :

a n ist die kleinste positive ganze Zahl, so dass a n - n ein ganzes Vielfaches von 3 ist und die doppelte Anzahl von Teilern von (a n - n) / 3 den n- ten Term in den ersten Differenzen der vom Flavius ​​erzeugten Sequenz ergibt Josephus Sieb.

Schon verloren? Nun, es ist eigentlich ganz einfach.

Das Flavius ​​Josephus-Sieb definiert eine ganzzahlige Folge wie folgt.

  1. Beginnen Sie mit der Folge positiver Ganzzahlen und setzen Sie k = 2 .

  2. Entferne jede k- te ganze Zahl der Sequenz, beginnend mit der k- ten .

  3. Inkrementiere k und gehe zurück zu Schritt 2.

f n ist die n- te Ganzzahl (1-indiziert), die niemals entfernt wird.

Wenn - wie üblich - σ 0 (k) die Anzahl der positiven Teiler der ganzen Zahl k bezeichnet , können wir ein n als die kleinste positive ganze Zahl definieren, so dass 0 ((a n - n) / 3) = f n + 1 ist - f n .

Herausforderung

Schreiben Sie ein Programm oder eine Funktion, die eine positive Ganzzahl n als Eingabe verwendet und eine n ausgibt oder zurückgibt .

Es gelten die Standardregeln für . Möge der kürzeste Code gewinnen!

Arbeitsbeispiele

Wenn wir jedes zweite Element der positiven ganzen Zahlen entfernen, bleibt uns nichts anderes übrig

 1  3  5  7  9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 ...

Nachdem wir jedes dritte Element des Restes entfernt haben, erhalten wir

 1  3  7  9 13 15 19 21 25 27 31 33 37 39 ...

Wenn wir nun jedes vierte, dann fünfte und dann sechste Element entfernen, erhalten wir

 1  3  7 13 15 19 25 27 31 37 39 ...
 1  3  7 13 19 25 27 31 39 ...
 1  3  7 13 19 27 31 39 ...
 1  3  7 13 19 27 39 ...

Die letzte Zeile zeigt die Terme f 1 bis f 7 .

Die Unterschiede der aufeinanderfolgenden Elemente dieser Begriffe sind

 2  4  6  6  8 12

Teilen Sie diese Vorwärtsdifferenzen durch 2 , erhalten wir

 1  2  3  3  4  6 

Dies sind die Zieldivisorenzahlen.

  • 4 ist die erste ganze Zahl k, so dass & sgr; 0 ((k - 1) / 3) = 1 ist . Tatsächlich ist σ 0 (1) = 1 .
  • 8 ist die erste ganze Zahl k, so dass & sgr; 0 ((k - 2) / 3) = 2 ist . In der Tat, & sgr; 0 (2) = 2 .
  • 15 ist die erste ganze Zahl k, so dass & sgr; 0 ((k - 3) / 3) = 3 ist . In der Tat, & sgr; 0 (4) = 3 .
  • 16 ist die erste ganze Zahl k, so dass & sgr; 0 ((k - 4) / 3) = 3 ist . In der Tat, & sgr; 0 (4) = 3 .
  • 23 ist die erste ganze Zahl k, so dass & sgr; 0 ((k - 5) / 3) = 4 ist . In der Tat, & sgr; 0 (6) = 4 .
  • 42 ist die erste ganze Zahl k, so dass & sgr; 0 ((k - 6) / 3) = 6 ist . In der Tat, & sgr; 0 (12) = 6 .

Testfälle

   n     a(n)

   1        4
   2        8
   3       15
   4       16
   5       23
   6       42
   7       55
   8      200
   9       81
  10       46
  11      119
  12      192
  13      205
  14   196622
  15    12303
  16       88
  17      449
  18      558
  19      127
  20     1748
  21   786453
  22       58
  23     2183
  24     3096
  25     1105
  26   786458
  27 12582939
  28      568
  29     2189
  30     2730
Dennis
quelle
14
Schlüsselwort auf OEIS: dumm ("eine unwichtige Sequenz").
Orlp
15
Dumm? Es könnte die Welt retten!
Dennis
3
Das Wortspiel aber ...
Mego

Antworten:

7

Jelly, 30 29 27 25 Bytes

2 Bytes gespart dank @Dennis, der mich benachrichtigt hat Æd, und weitere 2 Bytes für das Kombinieren der beiden Ketten.

RUð÷‘Ċ×µ/
‘Ç_ÇH0Æd=¥1#×3+

Probieren Sie es online!

Das war wahrscheinlich der Spaß, den ich je mit Jelly hatte. Ich habe mit der zweiten Zeile begonnen, die f n aus n mit der Formel in OEIS berechnet, und sie ist ziemlich schön.

Erläuterung

RUð ÷ 'Ċ × µ / Hilfsverbindung zur Berechnung von F n . Argument: n
R Zahlen abrufen [1..n]
 U Rückwärts
        / Reduzieren um "auf die nächsten 2 Vielfachen aufrunden":
   ÷ Teilen Sie durch die nächste Zahl
    'Inkrementiere, um ein Vielfaches zu überspringen
     Ċ Decke (aufrunden)
      × Mit der nächsten Zahl multiplizieren

'Ç_ÇH0Æd = ¥ 1 # × 3 + Hauptlink. Argument: n
'Inkrement n
 Ç Berechne F n + 1 
   Ç Berechne F n
  _ Subtrahieren
    H Durch 2 teilen
     0 1 # Suchen Sie ab 0 den ersten Kandidaten für (a n -n) / 3
                   das genügt ...
      Æd σ 0 ((a n -n) / 3)
        = = (F n + 1 -F n ) / 2
            × 3 Multiply um 3 zu drehen (eine n - n) / 3 in eine n -n
              + Addiere n, um aus n- n ein n zu machen
PurkkaKoodari
quelle
3

Python 2 , 121 119 118 Bytes

n=input();r=range(1,4**n);d=s,=r*1,
for k in r:del s[k::k+1];d+=sum(k%j<1for j in r)*2,
print d.index(s[n]-s[n-1])*3+n

Die Laufzeit sollte ungefähr 0 (16 n ) bei 0 (4 n ) Speichernutzung betragen. Ersetzen 4**ndurch 5<<n- was ich für ausreichend halte - würde dies dramatisch verbessern, aber ich bin nicht davon überzeugt, dass es für beliebig große Werte von n funktioniert .

Probieren Sie es online!

Asymptotisches Verhalten und Obergrenzen von a n

Definiere b n als (a n - n) / 3 , dh die kleinste positive ganze Zahl k, so dass σ 0 (k) = ½ (f n + 1 - f n ) .

Wie auf der OEIS-Seite angegeben, ist f n ~ ¼πn 2 , also f n + 1 - f n ~ ¼π (n + 1) 2 - ¼πn 2 = ¼π (2n + 1) ~ ½πn .

Auf diese Weise ½ (f n + 1 - f n ) ~ ¼πn . Wenn die tatsächliche Zahl eine Primzahl p ist , ist die kleinste positive ganze Zahl mit p- Teilern 2 p-1 , so dass b n durch 2 c n angenähert werden kann , wobei c n ~ ¼πn ist .

Daher gilt b n <4 n für ausreichend großes n , und da 2 ¼πn <2 n << (2 n ) 2 = 4 n ist , bin ich zuversichtlich, dass es keine Gegenbeispiele gibt.

Wie es funktioniert

n=input();r=range(1,4**n);d=s,=r*1,

Dies legt einige Referenzen für unseren iterativen Prozess fest.

  • n ist die Benutzereingabe: eine positive ganze Zahl.

  • r ist die Liste [1, ..., 4 n - 1] .

  • s ist eine Kopie von r .

    Wenn Sie die Liste einmal mit wiederholen, r*1wird eine flache Kopie erstellt. Wenn Sie also s ändern, wird r nicht geändert .

  • d wird als das Tupel initialisiert (n) .

    Dieser erste Wert ist nicht wichtig. Alle anderen Werte enthalten Divisoren für positive ganze Zahlen.

for k in r:del s[k::k+1];d+=sum(k%j<1for j in r)*2,

Für jede ganze Zahl k von 1 bis 4 n - 1 machen wir folgendes.

  • del s[k::k+1]Nimmt jede (k + 1) -te Ganzzahl in s - beginnend mit der (k + 1) -ten - und löscht diesen Slice aus s .

    Auf diese einfache Weise kann ein Anfangsintervall des Flavius-Josephus-Siebs in s gespeichert werden . Es wird viel mehr als die erforderlichen n + 1 anfänglichen Terme berechnet , aber die Verwendung einer einzelnen forSchleife zum Aktualisieren von s und d spart einige Bytes.

  • d+=sum(k%j<1for j in r)*2,zählt, wie viele Elemente von r k gleichmäßig teilen und fügt 0 (k) an d an .

    Da d als Singleton-Tupel initialisiert wurde, wird 0 (k) am Index k gespeichert .

print d.index(s[n]-s[n-1])*3+n

Dies findet den ersten Index von f n + 1 - f n in d , der das kleinste k ist, so dass 0 (k) = f n + 1 - f n ist , berechnet dann ein n als 3k + 1 und gibt das Ergebnis aus.

Dennis
quelle
2

Java 8, 336 , 305 , 303 , 287 , 283, 279 Bytes

57 Bytes dank Kritixi Lithos entfernt

Golf gespielt

class f{static int g(int s,int N){return s<1?N+1:g(s-1,N+N/s);}static int h(int k){int u=0,t=1,i;for(;u!=(g(k,k)-g(k,k-1))/2;t++)for(i=1,u=0;i<=t;)if(t%i++<1)u++;return 3*t-3+k;}public static void main(String[]a){System.out.print(h(new java.util.Scanner(System.in).nextInt()));}}

Ungolfed

class f {
    static int g(int s,int N){return s < 1 ? N + 1 : g(s - 1, N + N / s);}

    static int h(int k) {
        int u = 0, t = 1, i;
        // get the first number with v divisors
        while(u != (g(k, k) - g(k, k - 1))/2){
            u = 0;
            for (i = 1; i <= t; i++)
                if (t % i < 1) u++;
            t++;
        }
        // 3*(t-1)+k = 3*t+k-3
        return 3 * t + k - 3;
    }

    public static void main(String[] a) {
        System.out.print(h(new java.util.Scanner(System.in).nextInt()));
    }
}
Bobas_Pett
quelle
Ich denke, das Parsen der Befehlszeilenargumente intist kürzer als das Verwenden java.util.Scanner. Aber auch wenn Sie Scanner verwenden, können Sie System.out.print(h(new java.util.Scanner().nextInt()))die vorherige Zeile
Kritixi Lithos
@KritixiLithos thx, jetzt reparieren ...
Bobas_Pett
Im Inneren int h()können Sie es ändern int v = (g(k,k)-g(k,k-1))/2,u = 0,t = 1;. Sie können Ihre if-Anweisung (die sich in Ihrer for-Schleife befindet) von if(t%i==0)aufif(t%i<1)
Kritixi Lithos 27.12.16
Außerdem können Sie Ihre Funktion so ändern g, dass sie mit ternären Operatoren wie return s==0?N+1:g(s-1,N+N/2)-ish
Kritixi Lithos 27.12.16
2
@KritixiLithos lol an dieser Stelle u sollte dies nur als eigene separate Lösung veröffentlichen
Bobas_Pett
1

Mathematica, 130 116 106 103 Bytes

3Catch@Do[f=#2⌈#/#2+1⌉&~Fold~Reverse@Range@#&;If[Tr[2+0Divisors@k]==f[#+1]-f@#,Throw@k],{k,∞}]+#&

oder

3Catch@Do[f=#2⌈#/#2+1⌉&~Fold~Reverse@Range@#&;If[2DivisorSum[k,1&]==f[#+1]-f@#,Throw@k],{k,∞}]+#&

Am Ende war es fast identisch mit @ Pietu1998s Jelly-Code ...

Erläuterung

Catch@

Catchwas auch immer Throwgeworfen wird.

Do[ ... ,{k,∞}]

Endlosschleife; kgeht von 1jeder Iteration aus und inkrementiert sie.

f= ...

Zuweisen f:

Reverse@Range@#

Finden {1, 2, ... , n}. Dreh es um.

#2⌈#/#2+1⌉&

Eine Funktion, die ceil (n1 / n2 + 1) * n2 ausgibt

f= ... ~Fold~ ... &

Weisen Sie feine Funktion zu, die die obige Funktion rekursiv aus zwei Schritten auf die Liste anwendet, wobei jeder Ausgang als erster Eingang und jedes Element der Liste als zweiter Eingang verwendet wird. Die anfängliche "Ausgabe" (erste Eingabe) ist das erste Element der Liste.

Tr[2+0Divisors@k]==f[#+1]-f@#

Prüfen Sie, ob die doppelte Anzahl der Teiler von kgleich f (n + 1) - f (n) ist.

If[ ... ,Throw@k]

Wenn die Bedingung lautet True, ist Throwder Wert von k. Wenn nicht, fahren Sie mit der Schleife fort.

3 ... +#&

Multiplizieren Sie die Ausgabe mit 3 und addieren Sie n.

130-Byte-Version

Catch@Do[s=#+1;a=k-#;If[3∣a&&2DivisorSigma[0,a/3]==Differences[Nest[i=1;Drop[#,++i;;;;i]&,Range[s^2],s]][[#]],Throw@k],{k,∞}]&
JungHwan min
quelle
1

Perl 6 , 154 149 136 107 Bytes

->\n{n+3*first ->\o{([-] ->\m{m??&?BLOCK(m-1).rotor(m+0=>1).flat!!1..*}(n)[n,n-1])/2==grep o%%*,1..o},^Inf}

Ungolfed:

-> \n {                    # Anonymous sub taking argument n
  n + 3 * first -> \o {    # n plus thrice the first integer satisfying:
    (                      #
      [-]                  #
      -> \m {              # Compute nth sieve iteration:
        m                  # If m is nonzero,
          ?? &?BLOCK(m-1).rotor(m+0=>1).flat # then recurse and remove every (m+1)-th element;
          !! 1..*          # the base case is all of the positive integers
      }                    #
      (n)                  # Get the nth sieve
      [n,n-1]              # Get the difference between the nth and (n-1)th elements (via the [-] reduction operator above)
    ) / 2                  # and divide by 2;
    ==                     # We want the number that equals
    grep o %% *, 1..o      # the number of divisors of o.
  }
  ,^Inf
}
Sean
quelle
1

05AB1E ,35 34 39 Bytes

1Qi4ë[N3*¹+NÑg·¹D>‚vyy<LRvy/>îy*}}‚Æ(Q#

Es sieht schrecklich aus, genauso wie die Laufzeitleistung. Es dauert einige Sekunden, bis Eingaben kleine Werte ergeben. Versuche keine Zahlen wie 14; es wird schließlich das Ergebnis finden, aber es würde ewig dauern.

Erläuterung

Es funktioniert als 2 nacheinander aufgerufene Programme. Der erste berechnet F n + 1 - F n und der zweite bestimmt ein n basierend auf seiner Definition unter Verwendung eines Bruteforce-Ansatzes.

F n + 1 - F n wird für jede Iteration ausgewertet, obwohl sie schleifeninvariant ist. Dadurch wird die Codezeit ineffizient, aber der Code wird kürzer.

Probieren Sie es online!

Osable
quelle
Ich bin mir nicht sicher ob ich das verstehe. Warum kann das Sieb nicht über 65.536 berechnet werden?
Dennis
Dies ergibt sich aus der Tatsache, dass alle Ganzzahlen zwischen 0 und 65536 ( žHL) generiert werden und dann die Werte herausgefiltert werden, die die Siebbedingungen nicht erfüllen. Ich denke, der erste Teil dieses Programms sollte mit einer völlig anderen Herangehensweise umgeschrieben werden, um es golffähig zu machen.
Osable
Sofern dies nicht durch Einschränkungen (z. B. Ganzzahlen mit fester Breite) verhindert wird, sollten die Antworten für jede Eingabe funktionieren, sofern genügend Zeit und Speicher vorhanden sind.
Dennis
Deshalb habe ich mir einen anderen Siebalgorithmus ausgedacht. Es könnte golffähig sein, aber ich habe es in 05AB1E nicht besser gefunden. Es gibt jedoch ein Gegenbeispiel given enough time and memory, da ich bereits mehrere Antworten auf andere Fragen gesehen habe, die so langsam abliefen, dass es fast unmöglich war zu sagen, ob sie die richtige Ausgabe lieferten oder nicht. Aus diesem Grund habe ich die Siebberechnung von der Schleife genommen und es hat mich 2 Bytes gekostet.
Osable
Sie müssen Ihren Code nicht effizienter gestalten. Sie können die golfene / langsame Implementierung zu Ihrer Vorlage machen und die schnellere / längere als Randnotiz einfügen. Ich muss leider auf das dynamische Limit bestehen, auch wenn es ein Byte kostet.
Dennis