cp's OEIS Frontend

A003309 Ludic numbers: apply the same sieve as Eratosthenes, but cross off every k-th remaining number.

%I A003309 M0655 #129 Dec 22 2024 15:56:38
%S A003309 1,2,3,5,7,11,13,17,23,25,29,37,41,43,47,53,61,67,71,77,83,89,91,97,
%T A003309 107,115,119,121,127,131,143,149,157,161,173,175,179,181,193,209,211,
%U A003309 221,223,227,233,235,239,247,257,265,277,283,287,301,307,313
%N A003309 Ludic numbers: apply the same sieve as Eratosthenes, but cross off every k-th remaining number.
%C A003309 The definition can obviously only be applied from k = a(2) = 2 on: for k = 1, all remaining numbers would be deleted. - _M. F. Hasler_, Nov 02 2024
%D A003309 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003309 Donovan Johnson, <a href="/A003309/b003309.txt">Table of n, a(n) for n = 1..100000</a>
%H A003309 David Applegate, <a href="/A003309/a003309.txt">C program for A003309</a>.
%H A003309 Donovan Johnson, <a href="/A255420/a255420.txt">Ludic numbers computed up to A003309(1236290) = 23000711</a>.
%H A003309 OEIS Wiki, <a href="https://oeis.org/wiki/Ludic_numbers">Ludic numbers</a>.
%H A003309 Popular Computing (Calabasas, CA), <a href="/A003309/a003309.pdf">Sieves: Problem 43</a>, Vol. 2 (No. 13, Apr 1974), pp. 6-7. This is Sieve #1. [Annotated and scanned copy]
%H A003309 Rosettacode Wiki, <a href="http://rosettacode.org/wiki/Ludic_numbers">Ludic numbers</a>.
%H A003309 <a href="/index/Si#sieve">Index entries for sequences generated by sieves</a>
%F A003309 Complement of A192607; A192490(a(n)) = 1. - _Reinhard Zumkeller_, Jul 05 2011
%F A003309 From _Antti Karttunen_, Feb 23 2015: (Start)
%F A003309 a(n) = A255407(A008578(n)).
%F A003309 a(n) = A008578(n) + A255324(n).
%F A003309 (End)
%p A003309 ludic:= proc(N) local i, k,S,R;
%p A003309   S:= {$2..N};
%p A003309   R:= 1;
%p A003309   while nops(S) > 0 do
%p A003309     k:= S[1];
%p A003309     R:= R,k;
%p A003309     S:= subsop(seq(1+k*j=NULL, j=0..floor((nops(S)-1)/k)),S);
%p A003309   od:
%p A003309 [R];
%p A003309 end proc:
%p A003309 ludic(1000); # _Robert Israel_, Feb 23 2015
%t A003309 t = Range[2, 400]; r = {1}; While[Length[t] > 0, k = First[t]; AppendTo[r, k]; t = Drop[t, {1, -1, k}];]; r (* _Ray Chandler_, Dec 02 2004 *)
%o A003309 (PARI) t=vector(399,x,x+1); r=[1]; while(length(t)>0, k=t[1];r=concat(r,[k]);t=vector((length(t)*(k-1))\k,x,t[(x*k+k-2)\(k-1)])); r \\ _Phil Carmody_, Feb 07 2007
%o A003309 (PARI) A3309=[1]; next_A003309(n)=n<A3309[#A3309] || until(, my(k=(#A3309-1)\2); forstep(j=#A3309-k,2,-1, k+=1+k\(A3309[j]-1));A3309=concat(A3309,k+2); k+2>n && break); n+!if(n=setsearch(A3309,n+1,1),return(A3309[n])) \\ Should be made more efficient if n >> max(A3309). - _M. F. Hasler_, Nov 02 2024
%o A003309 {A003309(n) = while(n>#A3309, next_A003309(A3309[#A3309])); A3309[n]} \\ Should be made more efficient in case n >> #A3309. - _M. F. Hasler_, Nov 03 2024
%o A003309 (PARI) upto(nn)= my(r=List([1..nn]), p=1); while(p++<#r, my(k=r[p], i=p); while((i+=k)<=#r, listpop(~r, i); i--)); Vec(r); \\ _Ruud H.G. van Tol_, Dec 13 2024
%o A003309 (Haskell)
%o A003309 a003309 n = a003309_list !! (n - 1)
%o A003309 a003309_list = 1 : f [2..] :: [Int]
%o A003309    where f (x:xs) = x : f (map snd [(u, v) | (u, v) <- zip [1..] xs,
%o A003309                                              mod u x > 0])
%o A003309 -- _Reinhard Zumkeller_, Feb 10 2014, Jul 03 2011
%o A003309 (Scheme)
%o A003309 (define (A003309 n) (if (= 1 n) n (A255127bi (- n 1) 1))) ;; Code for A255127bi given in A255127.
%o A003309 ;; _Antti Karttunen_, Feb 23 2015
%o A003309 (Python)
%o A003309 remainders = [0]
%o A003309 ludics = [2]
%o A003309 N_MAX = 313
%o A003309 for i in range(3, N_MAX) :
%o A003309     ludic_index = 0
%o A003309     while ludic_index < len(ludics) :
%o A003309         ludic = ludics[ludic_index]
%o A003309         remainder = remainders[ludic_index]
%o A003309         remainders[ludic_index] = (remainder + 1) % ludic
%o A003309         if remainders[ludic_index] == 0 :
%o A003309             break
%o A003309         ludic_index += 1
%o A003309     if ludic_index == len(ludics) :
%o A003309         remainders.append(0)
%o A003309         ludics.append(i)
%o A003309 ludics = [1] + ludics
%o A003309 print(ludics)
%o A003309 # _Alexandre Herrera_, Aug 10 2023
%o A003309 (Python)
%o A003309 def A003309(): # generator of the infinite list of ludic numbers
%o A003309     L = [2, 3]; yield 1; yield 2; yield 3
%o A003309     while k := len(L)//2: # could take min{k | k >= L[-1-k]-1}
%o A003309         for j in L[-1-k::-1]: k += 1 + k//(j-1)
%o A003309         L.append(k+2); yield k+2
%o A003309 A003309_upto = lambda N=99: [t for t,_ in zip(A003309(),range(N))]
%o A003309 # _M. F. Hasler_, Nov 02 2024
%Y A003309 Without the initial 1 occurs as the leftmost column in arrays A255127 and A260717.
%Y A003309 Cf. A003310, A003311, A100464, A100585, A100586 (variants).
%Y A003309 Cf. A192503 (primes in sequence), A192504 (nonprimes), A192512 (number of terms <= n).
%Y A003309 Cf. A192490 (characteristic function).
%Y A003309 Cf. A192607 (complement).
%Y A003309 Cf. A260723 (first differences).
%Y A003309 Cf. A255420 (iterates of f(n) = A003309(n+1) starting from n=1).
%Y A003309 Subsequence of A302036.
%Y A003309 Cf. A237056, A237126, A237427, A235491, A255407, A255408, A255421, A255422, A260435, A260436, A260741, A260742 (permutations constructed from Ludic numbers).
%Y A003309 Cf. also A000959, A008578, A255324, A254100, A272565 (Ludic factor of n), A297158, A302032, A302038.
%Y A003309 Cf. A376237 (ludic factorial: cumulative product), A376236 (ludic Fortunate numbers).
%K A003309 nonn,easy,nice
%O A003309 1,2
%A A003309 _N. J. A. Sloane_
%E A003309 More terms from _David Applegate_ and _N. J. A. Sloane_, Nov 23 2004