Najmniejsza nieużywana liczba współdzieląca czynnik

11

To całkiem niezłe pytanie od młyna. Zdefiniuję sekwencję, a ty zagrasz w golfa kodem, aby wygenerować wpis z indeksem.

  • Pierwszy element w sekwencji to 2.

  • N-ty element w sekwencji to najmniejsza dodatnia liczba całkowita inna niż n i 1, dzieląca co najmniej jeden czynnik z n (inny niż 1), który nie pojawił się jeszcze na liście.

Przypadki testowe

Oto pierwsze 25 pozycji w sekwencji:

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

Powiązany (przesunięty o jeden) OEIS

code-golf number sequence permutations Ad Hoc Garf Hunter
źródło

Odpowiedzi:

3

Python 3 , 118 117 bajtów

-1 bajt dzięki 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

Wypróbuj online!

Kod jest dość nieefektywny (brutalnie wymusza wartość, która nie istniała w poprzednich wynikach, i oblicza poprzednie wyniki dla każdej nowej wartości), więc działa poprawnie, ale nie zalecałbym uruchamiania go na dużych liczbach.

notjagan
źródło
2
Mała wskazówka: Możesz zapisać nową linię, tworząc ją def f(n,i=3):i usuwając i=3linię
Cameron Aavik
115 bajtów .
Jonathan Frech,
2

Haskell , 60 59 bajtów

EDYTOWAĆ:

  • -1 bajt: @xnor wskazał, że all(/=x)jest krótszy niż x`notElem`.

f przyjmuje liczbę całkowitą i zwraca liczbę całkowitą.

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

Wypróbuj online!

To bardzo wykładniczy czas, więc TIO kończy się po 21, podczas gdy mój interpretowany GHCi osiągnął 22, zanim go właśnie zatrzymałem. Następujące o 9 bajtów dłuższe wersje zapamiętujące na liście łatwo przechodzą w tysiące:

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

Wypróbuj online!

  • f nużywa rozumienia listy do generowania kandydatów x, biorąc pierwszy mijający z !!0.
  • gcd x n>1sprawdza to xi nma wspólne czynniki.
  • ||n<2zwalnia n==1z wymogu dotyczącego czynnika.
  • all(/=x)$n:map f[1..n-1]sprawdza, xczy nie jest nani poprzedzającym elementem sekwencji.
Ørjan Johansen
źródło
@WheatWizard Hm, prawdopodobnie nie ma różnicy w tym przypadku. Po prostu przywykłem do robienia tego domyślnie. Jest to jedna z niewielu funkcji alfanumerycznych, która ma zdefiniowaną poprawność, która dobrze do niej pasuje.
Ørjan Johansen
1
all(/=x)$jest tam 1 raz krótszy
xnor
2

Brak wbudowanego GCD w C #, więc ...

C # (.NET Core) , 197 196 194 bajtów

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

Wypróbuj online!

Jeszcze raz powstrzymaj się od używania tego kodu do obliczania liczb w sekwencji dla n>30...

  • -1 bajt poprzez zmianę whilepętli GCD dla forpętli.
  • -2 bajty dzięki Kevin Cruijssen! Niezłe!
Charlie
źródło
1
a>0&b>0można a*b>0
grać w