Kleinste nicht verwendete Nummer, die einen Faktor teilt

11

Dies ist eine ziemlich einfache Frage. Ich werde eine Sequenz definieren und Sie spielen einen Code, um einen Eintrag mit einem Index auszugeben.

  • Der erste Punkt in der Sequenz ist 2.

  • Das n-te Element in der Sequenz ist die kleinste positive ganze Zahl außer n und 1, die mindestens einen Faktor mit n (außer 1) teilt, der noch nicht in der Liste enthalten ist.

Testfälle

Hier sind die ersten 25 Elemente in der Sequenz:

1  2
2  4
3  6
4  8
5  10
6  3
7  14
8  12
9  15
10 5
11 22
12 9
13 26
14 7
15 18
16 20
17 34
18 16
19 38
20 24
21 27
22 11
23 46
24 21
25 30

Verwandte (um eins versetzt) ​​OEIS

code-golf number sequence permutations Post Rock Garf Hunter
quelle

Antworten:

5

Gelee , 19 Bytes

R»2ɓ²Rg⁸>1Tḟ⁸ḟḢṭµ/Ṫ

Probieren Sie es online aus!

Dennis
quelle
Ich war so froh, dass ich Sie bei der Lyndon- Frage zur Wortfaktorisierung überfordert hatte , aber dann haben Sie mich damit geschlagen ... (im Ernst, obwohl dies eine großartige Antwort ist)
notjagan
3

Python 3 , 118 117 Bytes

-1 Byte dank Cameron Aavik !

import math
def f(n,i=3):
 if n<2:return 2
 while 1:
  if math.gcd(n,i)>1>(i in map(f,range(n)))<i!=n:return i
  i+=1

Probieren Sie es online aus!

Der Code ist ziemlich ineffizient (er erzwingt einen Wert, der in den vorherigen Ergebnissen nicht vorhanden ist, und berechnet die vorherigen Ergebnisse für jeden neuen Wert erneut), sodass er ordnungsgemäß funktioniert, ich würde jedoch nicht empfehlen, ihn mit großen Zahlen auszuführen.

notjagan
quelle
2
Kleiner Tipp: Sie können eine neue Zeile speichern, indem Sie def f(n,i=3):sie erstellen und entferneni=3
Cameron Aavik
115 Bytes .
Jonathan Frech
2

Haskell , 60 59 Bytes

BEARBEITEN:

  • -1 Byte: @xnor wies darauf hin, all(/=x)war kürzer als x`notElem`.

f Nimmt eine Ganzzahl und gibt eine Ganzzahl zurück.

f n=[x|x<-[2..],gcd x n>1||n<2,all(/=x)$n:map f[1..n-1]]!!0

Probieren Sie es online aus!

Dies ist eine sehr exponentielle Zeit, daher tritt bei TIO nach 21 eine Zeitüberschreitung auf, während mein interpretiertes GHCi auf 22 stieg, bevor ich es gerade stoppte. Die folgenden 9 Bytes längerer Versionen, die in einer Liste gespeichert werden, gehen leicht in die Tausende:

f n=[x|x<-[2..],gcd x n>1||n<2,all(/=x)$n:take(n-1)l]!!0
l=f<$>[1..]

Probieren Sie es online aus!

  • f nverwendet ein Listenverständnis, um Kandidaten zu generieren x, wobei der erste bestanden wird !!0.
  • gcd x n>1prüft das xund nhat gemeinsame Faktoren.
  • ||n<2Ausnahmen n==1von der Faktoranforderung.
  • all(/=x)$n:map f[1..n-1]prüft, ob xes sich weder um nein vorhergehendes Sequenzelement handelt.
Ørjan Johansen
quelle
@ WheatWizard Hm, wahrscheinlich kein Unterschied in diesem Fall. Ich bin es nur gewohnt, es standardmäßig zu tun. Es ist eine der wenigen alphanumerischen Funktionen, für die eine Fixität definiert wurde, die auf diese Weise gut passt.
Ørjan Johansen
1
all(/=x)$ist dort 1 kürzer
xnor
2

Keine integrierte GCD in C #, also ...

C # (.NET Core) , 197 196 194 Bytes

n=>{if(n<2)return 2;var p=new int[n-1];int i=0,a,b;for(;i<n-1;)p[i]=f(++i);for(i=2;;i++)if(n!=i){for(a=n,b=i;a*b>0;)if(a>b)a%=b;else b%=a;if(b!=1&a!=1&!System.Array.Exists(p,e=>e==i))return i;}}

Probieren Sie es online aus!

Verwenden Sie diesen Code erneut nicht, um Zahlen in der Reihenfolge für n>30...

  • -1 Byte durch Ändern der GCD- whileSchleife für eine forSchleife.
  • -2 Bytes danke an Kevin Cruijssen! Schön!
Charlie
quelle
1
a>0&b>0kann zua*b>0
Kevin Cruijssen