Les nombres x tels que x ^ 2 divisent 7 ^ x-1

16

Tâche

Il y a un ensemble de nombres x, tels que des x^2divisions 7^x-1.

Votre tâche consiste à trouver ces numéros. Étant donné une entrée de n, le code affichera le nième nombre qui suit cette règle.

Exemples 1-index

In   Out
3    3
9    24
31   1140

La séquence appropriée peut être trouvée ici .

Règles

La réponse la plus courte sera le gagnant *

Les règles de golf standard s'appliquent

Les échappatoires ne sont pas autorisées

Votre réponse peut être indexée 0 ou 1, veuillez l'indiquer dans votre réponse

George
la source
@nimi Je les ai notées lors de la planification et je ne les ai jamais mises en œuvre. J'ai mis à jour la question
George
Quelles sont les limites de n? Je peux donner le résultat correct avec n=9, mais cela n=10me pose déjà des problèmes.
briantist
@briantist Si vous obtenez le mauvais résultat pour des valeurs d'entrée plus élevées, votre réponse est fausse. Si cela prend juste beaucoup de temps, cela peut dépendre de l'implémentation.
mbomb007
Cela ne prend pas seulement beaucoup de temps. n=10me donne 32; c'est parce qu'il commence à utiliser le double au lieu des entiers et le mod est incorrect après cela. :(
briantist

Réponses:

8

Haskell, 34 octets

([x|x<-[1..],mod(7^x-1)(x^2)<1]!!)

Cela utilise une indexation basée sur 0. Exemple d'utilisation: ([x|x<-[1..],mod(7^x-1)(x^2)<1]!!) 30-> 1140.

C'est une mise en œuvre directe de la définition. Il construit une liste de tous les nombres xet sélectionne le nth.

nimi
la source
5

Pyth , 10 octets

e.f!%t^7Z*

Un programme qui prend l'entrée d'un entier et imprime une valeur à un index.

Essayez-le en ligne!

Comment ça fonctionne

e.f!%t^7Z*     Program. Input: Q
e.f!%t^7Z*ZZQ  Implicit variable fill
               Implicitly print
e              the last
 .f         Q  of the first Q positive integers Z
     t^7Z      for which 7^Z - 1
    %          mod
         *ZZ   Z^2
   !           is zero
TheBikingViking
la source
5

JavaScript (ES7), 40 octets

f=(n,i=1)=>n?f(n-!((7**++i-1)%i**2),i):i

Cela perd de la précision assez rapidement du fait que JS perd de la précision par 7**19. Voici une version ES6 de précision presque arbitraire:

f=(n,i=0)=>n?f(n-!(~-(s=++i*i,g=j=>j?g(j-1)*7%s:1)(i)%s),i):i

Cela se termine dans environ une seconde pour le cas de test 31.

Quelques approches plus longues:

f=(n,i=0)=>n?f(n-!(~-(s=>g=j=>j?g(j-1)*7%s:1)(++i*i)(i)%s),i):i
f=(n,i=0)=>n?f(n-!(s=++i*i,g=(j,n=1)=>j?g(j-1,n*7%s):~-n%s)(i),i):i
f=(n,i=0)=>n?f(n-!(s=>g=(j,n=1)=>j?g(j-1,n*7%s):~-n%s)(++i*i)(i),i):i
ETHproductions
la source
4

05AB1E , 11 octets

µ7Nm<NnÖiN¼

Essayez-le en ligne!

Pour une raison quelconque, je ne peux pas ½travailler µ7Nm<NnÖ½Nou je serais à égalité avec Pyth.

µ           # Loop until the counter equals n.
 7Nm<       # Calc 7^x+1.
     Nn     # Calc x^2.
       Ö    # Check divisibility.
        iN¼ # If divisible, push current x and increment counter.
            # Implicit loop end.
            # Implicitly return top of stack (x)

.

Urne de poulpe magique
la source
Oui, j'ai cette bizarrerie avec Ösur ma liste de correctifs depuis des mois, mais je ne me débrouille jamais pour y faire face. Quoi qu'il en soit, vous n'avez pas besoin Nque as µrenvoie automatiquement le dernier Nsi la pile est vide.
Emigna
4

Python 2 , 48 46 octets

Merci à @Dennis pour -2 octets!

f=lambda n,i=1:n and-~f(n-(~-7**i%i**2<1),i+1)

Une fonction récursive à un index qui prend l'entrée via un argument et renvoie le résultat.

Essayez-le en ligne!(Limite de récursivité augmentée pour permettre au cas de test final de s'exécuter)

Comment ça fonctionne

nest l'indice souhaité et iest la variable de comptage.

L'expression ~-7**i%i**2<1renvoie True(équivalent à 1) si i^2divise 7^i - 1et False(équivalent à 0) sinon. Chaque fois que la fonction est appelée, le résultat de l'expression est soustrait de n, décrémentant nchaque fois qu'un hit est trouvé; iest également incrémenté.

Le comportement de court-circuit de andsignifie que quand nest 0, 0est retourné; c'est le cas de base. Une fois cela atteint, la récursivité s'arrête et la valeur actuelle de iest renvoyée par l'appel de fonction d'origine. Plutôt que d'utiliser explicitement i, cela se fait en utilisant le fait que pour chaque appel de fonction, un incrément a été effectué en utilisant le -~devant de l'appel; incrémenter les 0 itemps donne i, au besoin.

TheBikingViking
la source
1
(~-7**i%i**2<1)enregistre quelques octets.
Dennis
@Dennis Bien sûr! Merci.
TheBikingViking
3

Python 2 , 57 53 51 octets

-4 octets grâce à ETHproductions
-2 octets grâce à TuukkaX

i=0
g=input()
while g:i+=1;g-=~-7**i%i**2<1
print i

Essayez-le en ligne!
la séquence est indexée 1

Barre
la source
@ETHproductions yep c:
Rod
Un testcase échoue-t-il si vous supprimez les parenthèses autour (7**i)? Je les ai retirés et cela a fonctionné pour ceux que j'ai essayés.
Yytsi
@TuukkaX a en effet **une priorité plus élevée que ~et-
Rod
2

Python 2, 57 octets

Cela prend un temps vraiment très long pour les grandes valeurs. Il utilise également beaucoup de mémoire, car il construit la liste entière bien plus loin que nécessaire. Le résultat est indexé zéro.

lambda n:[x for x in range(1,2**n+1)if(7**x-1)%x**2<1][n]

Essayez-le en ligne

mbomb007
la source
par curiosité, existe-t-il une preuve de la 2**n+1limite supérieure?
Rod
@Rod Pas que je sache, mais étant donné qu'il y a 50 valeurs <5000, je suis sûr qu'il y en a beaucoup plus que 50 < 2**50. Je pourrais utiliser 9**n+9, mais cela prend beaucoup plus de temps. J'ai commencé à courir il y a f(20)quelque temps (avec 2**n+1); il n'est toujours pas terminé.
mbomb007
Je ne pense même pas qu'il y ait une preuve que la séquence est infinie, encore moins une belle borne supérieure pour le nième terme!
Greg Martin
2

Mathematica, 43 octets

J'ai actuellement trois solutions différentes pour ce nombre d'octets:

Nest[#+1//.x_/;!(x^2∣(7^x-1)):>x+1&,0,#]&
Nest[#+1//.x_/;Mod[7^x-1,x^2]>0:>x+1&,0,#]&
Nest[#+1//.x_:>x+Sign@Mod[7^x-1,x^2]&,0,#]&
Martin Ender
la source
Quel est le caractère entre x ^ 2 et (7 ^ x ... dans la première ligne? Il ressemble à un tuyau mais plus court
Sefa
@Sefa C'est le caractère Unicode du symbole mathématique "divise" et est utilisé par Mathematica comme opérateur pour Divisible.
Martin Ender
En voici un à 41 octets: Cases[Range[#^3],x_/;x^2∣(7^x-1)][[#]]&basé sur l'argument heuristique selon lequel n ^ 3 est une borne supérieure. J'en ai découvert une preuve vraiment merveilleuse, que cette marge est trop étroite pour contenir :)
Kelly Lowder
2

PARI / GP , 42 octets

Assez simple. 1 indexé, bien que cela puisse facilement être modifié.

n->=k=1;while(n--,while((7^k++-1)%k^2,));k

ou

n->=k=1;for(i=2,n,while((7^k++-1)%k^2,));k
Charles
la source
1

Python 3 , 45 octets

f=lambda n,k=2:n<2or-~f(n-(7**k%k**2==1),k+1)

Renvoie True pour l'entrée 1 , ce qui est autorisé par défaut .

Essayez-le en ligne!

Dennis
la source
Je ne peux pas tester cela pour le moment, mais je suppose qu'il renvoie une valeur pour d'autres entrées? Plutôt qu'un booléen?
George
1

R, 35 octets

Cela ne fonctionne que pour n<=8.

z=1:20;which(!(7^z-1)%%z^2)[scan()]

Cependant, voici une version plus longue qui fonctionne n<=25, pour 50 octets :

z=1:1e6;which(gmp::as.bigz(7^z-1)%%z^2==0)[scan()]
rturnbull
la source
Est-ce que cela ne fonctionne que 8parce qu'il devient un long int?
George
1
@george Oui, vous perdez la précision car R par défaut est un entier 32 bits. La deuxième version du code utilise un package gmp, qui autorise des entiers arbitrairement grands. Cependant, je manque rapidement de RAM pour calculer quoi que ce soit ci-dessus n=25.
rturnbull
0

PHP, 47 49 octets

while($n<$argv[1])$n+=(7**++$x-1)%$x**2<1;echo$x;

Fonctionne uniquement pour n <9 ( 7**9est plus grand PHP_INT_MAXqu'avec 64 bits)

62 octets utilisant des entiers de longueur arbitraire: (non testé; PHP sur ma machine n'a pas bcmath)

for($x=$n=1;$n<$argv[1];)$n+=bcpowmod(7,++$x,$x**2)==1;echo$x;

Courez avec php -nr '<code>' <n>.

pseudo code

implicit: $x = 0, $n = 0
while $n < first command line argument
    increment $x
    if equation is satisfied
        increment $n
print $x
Titus
la source
0

Pyke, 10 octets

~1IX7i^tR%

Essayez-le ici!

~1         -  infinite(1)
  IX7i^tR% - filter(^, not V)
    7i^    -    7**i
       t   -   ^-1
        R% -  ^ % v
   X       -   i**2
           - implicit: print nth value
Bleu
la source
0

Clojure , 83 octets

(fn[n](nth(filter #(= 0(rem(-(reduce *(repeat % 7N))1)(* % %)))(iterate inc 1N))n))

Essayez-le en ligne!

Cela crée une liste infinie de Java BigIntegers commençant à 1 et les filtre par la définition. Il utilise une indexation à base zéro pour sélectionner la n ème valeur dans la liste filtrée.

miles
la source
0

Perl 5, 35 octets

Eh bien, cela manquait, alors voici:

map{$_ if!((7**$_-1)%($_**2))}1..<>

ChatterOne
la source
0

Powershell, trop d'octets

Juste pour voir si c'était possible et ça l'est.

[System.Linq.Enumerable]::Range(1,10000)|?{[System.Numerics.BigInteger]::Remainder([System.Numerics.BigInteger]::Pow(7,$_)-1,$_*$_) -eq 0}
Jessica
la source
0

Perl 6 , 35 34 octets

{grep({(7**$_-1)%%$_²},^∞)[$_]}

0 indexé.

Rasé d'un octet grâce à Brad Gilbert.

Sean
la source
grep est un sous-programme, vous pouvez donc supprimer l'espace si vous mettez les parens après{grep(…)}
Brad Gilbert b2gills
0

QBIC , 39 octets

:{~(7^q-1)%(q^2)=0|b=b+1]~b=a|_Xq\q=q+1

Je ne pouvais pas le faire fonctionner dans QBasic 4.5, mais il semble fonctionner correctement dans QB64. Pour une raison inexplicable, QBasic refuse de diviser proprement 13 841 287 200 par 144, mais donne à la place un reste de -128. Il renvoie ensuite 16 comme le 7ème terme de cette séquence au lieu de 12 ...

:{      get N from the command line, start an infinite DO-loop
~       IF
(7^q-1) Part 1 of the formula (Note that 'q' is set to 1 as QBIC starts)
%       Modulus
(q^2)   The second part
=0      has no remainder
|b=b+1  Then, register a 'hit'
]       END IF
~b=a    If we have scored N hits
|_Xq    Quit, printing the last used number (q)
\q=q+1  Else, increase q by 1. 
        [DO-loop and last IF are implicitly closed by QBIC]
steenbergh
la source
0

Wonder , 28 octets

@:^#0(!>@! % - ^7#0 1^#0 2)N

Zéro indexé. Usage:

(@:^#0(!>@! % - ^7#0 1^#0 2)N)2

Filtre à partir de la liste des nombres naturels avec un prédicat qui détermine s'il x^2est divisible par 7^x-1, puis obtient le nième élément de cette liste.

Mama Fun Roll
la source
0

Tcl , 73 octets

while {[incr i]} {if 0==(7**$i-1)%$i**2 {incr j;if $j==$n break}}
puts $i

Essayez-le en ligne!

sergiol
la source