Votre tâche consiste à implémenter la séquence entière A130826 :

a _n est le plus petit entier positif tel que a _n - n est un multiple entier de 3 et le double du nombre de diviseurs de (a _n - n) / 3 donne le n ^ème terme dans les premières différences de la séquence produite par Flavius Tamis de Josephus.

Encore perdu? Eh bien, c'est en fait assez simple.

Le tamis Flavius ​​Josephus définit une séquence entière comme suit.

1. Commencez avec la séquence d'entiers positifs et définissez k = 2 .

2. Supprimez chaque k ^ème entier de la séquence, en commençant par le k ^ème .

3. Incrémentez k et revenez à l'étape 2.

f _n est la n ^ième nombre entier (1-indexé) qui n'est jamais enlevée.

Si - comme d'habitude - σ ₀ (k) désigne le nombre de diviseurs positifs de l'entier k , nous pouvons définir a _n comme le plus petit entier positif tel que 2σ ₀ ((a _n - n) / 3) = f _{n + 1} - f _n .

Défi

Écrivez un programme ou une fonction qui prend un entier positif n en entrée et imprime ou retourne un _n .

Les règles de code-golf standard s'appliquent. Que le code le plus court gagne!

Exemples travaillés

Si nous supprimons chaque deuxième élément des entiers positifs, nous nous retrouvons avec

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

Après avoir retiré chaque troisième élément du reste, nous obtenons

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

Maintenant, en supprimant chaque quatrième, puis cinquième, puis sixième élément nous obtient

 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 ...

La dernière ligne montre les termes f ₁ à f ₇ .

Les différences des éléments consécutifs de ces termes sont

 2  4  6  6  8 12

En divisant ces différences avant par 2 , nous obtenons

 1  2  3  3  4  6 

Ce sont les nombres de diviseurs cibles.

• 4 est le premier entier k tel que σ ₀ ((k - 1) / 3) = 1 . En fait, σ ₀ (1) = 1 .
• 8 est le premier entier k tel que σ ₀ ((k - 2) / 3) = 2 . En fait, σ ₀ (2) = 2 .
• 15 est le premier entier k tel que σ ₀ ((k - 3) / 3) = 3 . En fait, σ ₀ (4) = 3 .
• 16 est le premier entier k tel que σ ₀ ((k - 4) / 3) = 3 . En fait, σ ₀ (4) = 3 .
• 23 est le premier entier k tel que σ ₀ ((k - 5) / 3) = 4 . En fait, σ ₀ (6) = 4 .
• 42 est le premier entier k tel que σ ₀ ((k - 6) / 3) = 6 . En fait, σ ₀ (12) = 6 .

Cas de test

   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

Gelée, 30 29 27 25 octets

Sauvegardé 2 octets grâce à @Dennis m'avertissant Ædet 2 autres octets pour avoir combiné les deux chaînes.

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

Essayez-le en ligne!

Ce fut probablement le plus amusant que j'ai jamais eu avec Jelly. Je suis parti de la deuxième ligne, qui calcule f _{n à} partir de n en utilisant la formule sur OEIS, et c'est assez beau.

Explication

RUð ÷ 'Ċ × µ / Lien d'aide pour calculer F n . Argument: n
R Obtenir des nombres [1..n]
 U inverse
        / Réduire de "arrondir aux 2 multiples suivants":
   ÷ Diviser par le nombre suivant
    'Incrément pour sauter un multiple
     Ċ Ceil (arrondi)
      × Multipliez par le nombre suivant

'Ç_ÇH0Æd = ¥ 1 # × 3 + Lien principal. Argument: n
'Incrément n
 Ç Calculer F n + 1 
   Ç Calculer F n
  _ Soustraire
    H Diviser par 2
     0 1 # A partir de 0, trouver le premier candidat pour (a n -n) / 3
                   qui satisfait ...
      Æd σ 0 ((a n -n) / 3)
        = = (F n + 1 -F n ) / 2
            × 3 Multipliez par 3 pour transformer (a n -n) / 3 en n -n
              + Ajouter n pour transformer un n -n en un n

Python 2 , 121 119 118 118 octets

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

Le temps d'exécution doit être d'environ O (16 ⁿ ) avec une utilisation de mémoire O (4 ⁿ ) . Remplacer 4**npar 5<<n- ce qui me semble suffisant - améliorerait considérablement cela, mais je ne suis pas convaincu que cela fonctionne pour des valeurs arbitrairement grandes de n .

Essayez-le en ligne!

Comportement asymptotique et limites supérieures d'un _n

Définissons b _n comme (a _n - n) / 3 , c'est-à-dire le plus petit entier positif k tel que σ ₀ (k) = ½ (f _{n + 1} - f _n ) .

Comme indiqué sur la page OEIS, f _n ~ ¼πn ² , donc f _{n + 1} - f _n ~ ¼π (n + 1) ² - ¼πn ² = ¼π (2n + 1) ~ ½πn .

De cette façon, ½ (f _{n + 1} - f _n ) ~ ¼πn . Si le nombre réel est un p premier , le plus petit entier positif avec p diviseurs est 2 ^p-1 , donc b _n peut être approximé par 2 ^{c _n} , où c _n ~ ¼πn .

Par conséquent, b _n <4 ⁿ tiendra pour suffisamment grand n , et étant donné que 2 ^¼πn <2 ⁿ << (2 ⁿ ) ² = 4 ⁿ , je suis convaincu qu'il n'y a pas de contre-exemples.

Comment ça marche

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

Cela établit quelques références pour notre processus itératif.

• n est l'entrée utilisateur: un entier positif.

• r est la liste [1, ..., 4 ⁿ - 1] .

• s est une copie de r .

  Répéter la liste une fois avec r*1crée une copie superficielle, donc la modification de s ne modifiera pas r .

• d est initialisé en tant que tuple (s) .

  Cette première valeur n'est pas importante. Tous les autres contiendront des nombres diviseurs d'entiers positifs.

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

Pour chaque entier k de 1 à 4 ⁿ - 1 , nous procédons comme suit.

• del s[k::k+1]prend chaque (k + 1) ^e entier de s - en commençant par le (k + 1) ^e - et supprime cette tranche de s .

  Ceci est un moyen simple consistant à stocker un intervalle initial de l'Josephus Flavius tamis en s . Il calculera beaucoup plus que les termes initiaux n + 1 requis , mais l'utilisation d'une seule forboucle pour mettre à jour s et d économise quelques octets.

• d+=sum(k%j<1for j in r)*2,compte le nombre d'éléments de r divise k également et ajoute 2σ ₀ (k) à d .

  Puisque d a été initialisé en tant que tuple singleton, 2σ ₀ (k) est stocké à l'indice k .

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

Ceci trouve le premier indice de f _{n + 1} - f _n dans d , qui est le plus petit k tel que 2σ ₀ (k) = f _{n + 1} - f _n , puis calcule un _n comme 3k + 1 et imprime le résultat.

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

57 octets supprimés grâce à Kritixi Lithos

Golfé

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()));
    }
}

Mathematica, 130 116 106 103 103 octets

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

ou

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

A fini par être presque identique au code Jelly de @ Pietu1998 ...

Explication

Catch@

Catchtout ce qui est Throw-ed (jeté).

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

Boucle infinie; kdémarre 1et incrémente chaque itération.

f= ...

Attribuer f:

Reverse@Range@#

Trouvez {1, 2, ... , n}. Inversez-le.

#2⌈#/#2+1⌉&

Une fonction qui produit ceil (n1 / n2 + 1) * n2

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

Attribuez fune fonction qui applique récursivement la fonction ci-dessus à la liste à partir de deux étapes ci-dessus, en utilisant chaque sortie comme première entrée et chaque élément de la liste comme deuxième entrée. La "sortie" initiale (première entrée) est le premier élément de la liste.

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

Vérifiez si deux fois le nombre de diviseurs de kest égal à f (n + 1) - f (n).

If[ ... ,Throw@k]

Si la condition est True, Throwla valeur de k. Sinon, continuez la boucle.

3 ... +#&

Multipliez la sortie par 3 et ajoutez n.

Version 130 octets

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,∞}]&

Perl 6 , 154 149 136 136 107 octets

->\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
}

05AB1E ,35 34 39 octets

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

Cela a l'air horrible, tout comme les performances d'exécution. Cela prend plusieurs secondes pour une entrée qui donne de petites valeurs. N'essayez pas des nombres comme 14; il finira par trouver le résultat mais cela prendra des âges.

Explication

Il fonctionne comme 2 programmes appelés séquentiellement. Le premier calcule F _{n + 1} - F _n et le second détermine un _{n en} fonction de sa définition, en utilisant une approche de force brute.

F _{n + 1} - F _n est évalué pour chaque itération même s'il est invariant en boucle. Cela rend le code inefficace, mais il raccourcit le code.

Essayez-le en ligne!