A302036 -id:A302036 - cp's OEIS frontend

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

1, 2, 3, 5, 7, 11, 13, 17, 23, 25, 29, 37, 41, 43, 47, 53, 61, 67, 71, 77, 83, 89, 91, 97, 107, 115, 119, 121, 127, 131, 143, 149, 157, 161, 173, 175, 179, 181, 193, 209, 211, 221, 223, 227, 233, 235, 239, 247, 257, 265, 277, 283, 287, 301, 307, 313

Offset: 1

N. J. A. Sloane

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

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Donovan Johnson, Table of n, a(n) for n = 1..100000
David Applegate, C program for A003309.
Donovan Johnson, Ludic numbers computed up to A003309(1236290) = 23000711.
OEIS Wiki, Ludic numbers.
Popular Computing (Calabasas, CA), Sieves: Problem 43, Vol. 2 (No. 13, Apr 1974), pp. 6-7. This is Sieve #1. [Annotated and scanned copy]
Rosettacode Wiki, Ludic numbers.
Index entries for sequences generated by sieves

Without the initial 1 occurs as the leftmost column in arrays A255127 and A260717.
Cf. A003310, A003311, A100464, A100585, A100586 (variants).
Cf. A192503 (primes in sequence), A192504 (nonprimes), A192512 (number of terms <= n).
Cf. A192490 (characteristic function).
Cf. A192607 (complement).
Cf. A260723 (first differences).
Cf. A255420 (iterates of f(n) = A003309(n+1) starting from n=1).
Subsequence of A302036.
Cf. A237056, A237126, A237427, A235491, A255407, A255408, A255421, A255422, A260435, A260436, A260741, A260742 (permutations constructed from Ludic numbers).
Cf. also A000959, A008578, A255324, A254100, A272565 (Ludic factor of n), A297158, A302032, A302038.
Cf. A376237 (ludic factorial: cumulative product), A376236 (ludic Fortunate numbers).

a003309 n = a003309_list !! (n - 1)
a003309_list = 1 : f [2..] :: [Int]
   where f (x:xs) = x : f (map snd [(u, v) | (u, v) <- zip [1..] xs,
                                             mod u x > 0])
-- Reinhard Zumkeller, Feb 10 2014, Jul 03 2011

ludic:= proc(N) local i, k,S,R;
  S:= {$2..N};
  R:= 1;
  while nops(S) > 0 do
    k:= S[1];
    R:= R,k;
    S:= subsop(seq(1+k*j=NULL, j=0..floor((nops(S)-1)/k)),S);
  od:
[R];
end proc:
ludic(1000); # Robert Israel, Feb 23 2015

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 *)

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

A3309=[1]; next_A003309(n)=nn && 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
{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

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

remainders = [0]
ludics = [2]
N_MAX = 313
for i in range(3, N_MAX) :
    ludic_index = 0
    while ludic_index < len(ludics) :
        ludic = ludics[ludic_index]
        remainder = remainders[ludic_index]
        remainders[ludic_index] = (remainder + 1) % ludic
        if remainders[ludic_index] == 0 :
            break
        ludic_index += 1
    if ludic_index == len(ludics) :
        remainders.append(0)
        ludics.append(i)
ludics = [1] + ludics
print(ludics)
# Alexandre Herrera, Aug 10 2023

def A003309(): # generator of the infinite list of ludic numbers
    L = [2, 3]; yield 1; yield 2; yield 3
    while k := len(L)//2: # could take min{k | k >= L[-1-k]-1}
        for j in L[-1-k::-1]: k += 1 + k//(j-1)
        L.append(k+2); yield k+2
A003309_upto = lambda N=99: [t for t,_ in zip(A003309(),range(N))]
# M. F. Hasler, Nov 02 2024

(define (A003309 n) (if (= 1 n) n (A255127bi (- n 1) 1))) ;; Code for A255127bi given in A255127.
;; Antti Karttunen, Feb 23 2015

Complement of A192607; A192490(a(n)) = 1. - Reinhard Zumkeller, Jul 05 2011
From Antti Karttunen, Feb 23 2015: (Start)
a(n) = A255407(A008578(n)).
a(n) = A008578(n) + A255324(n).
(End)

More terms from David Applegate and N. J. A. Sloane, Nov 23 2004

A272565 Smallest ludic factor of n.

Original entry on oeis.org

1, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 5, 2, 3, 2, 23, 2, 25, 2, 3, 2, 29, 2, 7, 2, 3, 2, 5, 2, 37, 2, 3, 2, 41, 2, 43, 2, 3, 2, 47, 2, 5, 2, 3, 2, 53, 2, 11, 2, 3, 2, 7, 2, 61, 2, 3, 2, 5, 2, 67, 2, 3, 2, 71, 2, 13, 2, 3, 2, 77, 2, 5, 2, 3

Offset: 1

Max Barrentine, May 09 2016

nonn

This sequence is somewhat analogous to the smallest prime factor of n (A020639). However, each natural number has only one ludic factor, because once it is crossed off in the k-th step of the sieve process, it is not a member of the terms considered in the (k+1)-th step.
On the other hand, by iteratively invoking A302032 it is possible to factor n to its constituent "Ludic factors", with each natural number having a unique such decomposition, analogous to prime factorization of n. See comments and examples given in A302032. - Antti Karttunen, Apr 08 2018
The "ludic factor" here is the k which either yields one of the ludic numbers A003309, or is used to cross out a non ludic number. In that case, this "ludic factor" often does not divide n, see A276569. But in the usual sieve of Eratosthenes, the fact that numbers are crossed out from the list does not mean they don't have other factors, so exactly the same could be considered here, which makes disputable the assertion that numbers have only one ludic factor. - M. F. Hasler, Nov 03 2024

Max Barrentine, Table of n, a(n) for n = 1..10000
OEIS Wiki, Ludic numbers.
Index entries for sequences generated by sieves

Cf. A003309 (ludic numbers), A020639 (least prime factor), A027748 (prime factors of n), A192607, A255127, A260738, A276440, A276568, A276569, A302032.
Cf. A276347, A276447, A276448 (ludic factor is equal, less than or greater than the smallest prime factor).
Cf. A260739 (ordinal transform), A302036 (numbers with all Ludic factors equal).
Cf. A264940 (analogous version for lucky numbers).

apply( {A272565(n)=A003309(A260738(n)+1)}, [1..99]) \\ M. F. Hasler, Nov 03 2024

(define (A272565 n) (A003309 (+ 1 (A260738 n)))) ;; Antti Karttunen, Sep 11 2016

From Antti Karttunen, Sep 11 2016: (Start)
a(n) = A003309(1 + A260738(n)).
For all n >= 1, a(A276347(n)) = A020639(A276347(n)). (End)
From M. F. Hasler, Nov 04 2024: (Start)
To rephrase the above: By definition, k is in A276347 iff a(k) = A020639(k).
Particular cases: a(2n) = 2 and a(6n-3) = 3 for all n. (End)

Added "smallest" in the definition because the explanation of "only one..." in the first comment might be disputable. - M. F. Hasler, Nov 03 2024

A260739 Column index to A255127: a(1) = 1; for n > 1, a(n) = the position at the stage where n is removed in the sieve which produces Ludic numbers.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 4, 2, 5, 1, 6, 1, 7, 3, 8, 1, 9, 2, 10, 4, 11, 1, 12, 1, 13, 5, 14, 1, 15, 2, 16, 6, 17, 3, 18, 1, 19, 7, 20, 1, 21, 1, 22, 8, 23, 1, 24, 4, 25, 9, 26, 1, 27, 2, 28, 10, 29, 3, 30, 1, 31, 11, 32, 5, 33, 1, 34, 12, 35, 1, 36, 2, 37, 13, 38, 1, 39, 6, 40, 14, 41, 1, 42, 4, 43, 15, 44, 1, 45, 1, 46, 16, 47, 7, 48, 1, 49, 17, 50, 2

Offset: 1

Antti Karttunen, Jul 30 2015

nonn

Ordinal transform of A272565 (Ludic factor), and also of A260738. - Antti Karttunen, Apr 03 2018

Antti Karttunen, Table of n, a(n) for n = 1..10105

Column index to array A255127.
Cf. A003309, A254100, A272565.
Cf. A260738 (corresponding row index).
Cf. A302035, A302036 (positions of terms that are powers of 2).
Cf. A078898, A246277, A260429, A260439 for column indices to other arrays similar to A255127.
Differs from A246277 (and also after the initial term from A078898) for the first time at n=19.

(define (A260739 n) (cond ((= 1 n) 1) ((even? n) (/ n 2)) (else (let searchrow ((row 2)) (let searchcol ((col 1)) (cond ((>= (A255127bi row col) n) (if (= (A255127bi row col) n) col (searchrow (+ 1 row)))) (else (searchcol (+ 1 col))))))))) ;; Code for A255127bi given in A255127.

Other identities. For all n >= 2:
a(A003309(n)) = 1. [In Ludic sieve each Ludic number (after 1) is the first among the numbers removed at stage k.]
a(A254100(n)) = 2.
A255127(A260738(n), a(n)) = n.
For n > 1, A001511(a(n)) = A302035(n). - Antti Karttunen, Apr 03 2018

Term a(1) changed from 0 to 1 to match with the definition of A078898 and the interpretation as an ordinal transform - Antti Karttunen, Apr 03 2018

A254100 Postludic numbers: Second column of Ludic array A255127.

Original entry on oeis.org

4, 9, 19, 31, 55, 73, 101, 145, 167, 205, 253, 293, 317, 355, 413, 473, 521, 569, 623, 677, 737, 763, 833, 917, 983, 1027, 1051, 1121, 1171, 1273, 1337, 1411, 1471, 1571, 1619, 1663, 1681, 1807, 1957, 1991, 2087, 2113, 2171, 2245, 2275, 2335, 2401, 2497, 2593, 2713, 2771, 2831, 2977, 3047, 3113

Offset: 1

Antti Karttunen, Feb 22 2015

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10001

Column 2 of A255127. (Row 2 of A255129). Positions of 2's in A260739.
Subsequence of A192607, A302036 and A302038.
Cf. A276576, A276606 (first differences).
Cf. also A001248, A219178.

rows = 100; cols = 2; t = Range[2, 10^4]; r = {1}; n = 1; While[n <= rows, k = First[t]; AppendTo[r, k]; t0 = t; t = Drop[t, {1, -1, k}]; ro[n++] = Complement[t0, t][[1 ;; cols]]]; A = Array[ro, rows]; Table[A[[n, 2]], {n, 1, rows} ] (* Jean-François Alcover, Mar 14 2016, after Ray Chandler *)

(define (A254100 n) (A255127bi n 2)) ;; A255127bi given in A255127.

a(n) = A255407(A001248(n)).

A302034 A028234 analog for a factorization process based on the Ludic sieve (A255127); Discard all instances of the (smallest) Ludic factor A272565(n) from n.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 1, 5, 1, 3, 1, 7, 5, 1, 1, 9, 1, 5, 1, 11, 1, 3, 1, 13, 7, 7, 1, 15, 1, 1, 5, 17, 7, 9, 1, 19, 11, 5, 1, 21, 1, 11, 1, 23, 1, 3, 1, 25, 19, 13, 1, 27, 1, 7, 7, 29, 11, 15, 1, 31, 13, 1, 11, 33, 1, 17, 5, 35, 1, 9, 1, 37, 17, 19, 1, 39, 7, 5, 11, 41, 1, 21, 1, 43, 35, 11, 1, 45, 1, 23, 1, 47, 13, 3, 1, 49, 23, 25, 1, 51, 13, 13, 19

Offset: 1

Antti Karttunen, Apr 01 2018

nonn

Iterating n, a(n), a(a(n)), a(a(a(n))), ..., until 1 is reached, and taking the Ludic factor (A272565) of each term gives a sequence of distinct Ludic numbers (A003309) in ascending order, while applying A302035 to the same terms gives the corresponding "exponents" of these Ludic factors in this nonstandard "Ludic factorization of n", unique for each natural number n >= 1. Permutation pair A302025/A302026 maps between this Ludic factorization and the ordinary prime factorization of n. See also comments and examples in A302032.

Antti Karttunen, Table of n, a(n) for n = 1..32768
Index entries for sequences generated by sieves

Cf. A003309, A255127, A260738, A260739, A269379, A269380, A302025, A302026, A302032, A302035.
Cf. A302036 (gives the positions of 1's).
Cf. also A028234, A302044.

\\ Assuming A269379 and its inverse A269380 have been precomputed, then the following is reasonably fast:
A302034(n) = if(1==n,n,my(k=0); while((n%2), n = A269380(n); k++); n = (n/2^valuation(n, 2)); while(k>0, n = A269379(n); k--); (n));

For n > 1, a(n) = A269379^(r)(A000265(A260739(n))), where r = A260738(n)-1 and A269379^(r)(n) stands for applying r times the map x -> A269379(x), starting from x = n.

a(n) = A302025(A028234(A302026(n))).

A302031 An omega (A001221) analog based on the Ludic sieve (A255127): a(1) = 0; for n > 1, a(n) = 1 + a(A302034(n)).

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 2, 3, 1, 2, 2, 1, 2, 3, 1, 2, 2, 3, 1, 2, 1, 2, 2, 2, 1, 3, 2, 2, 2, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 1, 3, 2, 2, 2

Offset: 1

Antti Karttunen, Apr 02 2018

nonn

Antti Karttunen, Table of n, a(n) for n = 1..32768
Index entries for sequences generated by sieves

Cf. A001221, A302026, A302037, A302041,
Cf. A302036 (positions of terms < 2).
Differs from similar A302041 for the first time at n=59, where a(59) = 2, while A302041(59) = 1.

\\ Assuming that A269379 and A269380 have been precomputed:
A302034(n) = if(1==n,n,my(k=0); while((n%2), n = A269380(n); k++); n = (n/2^valuation(n, 2)); while(k>0, n = A269379(n); k--); (n));
A302031(n) = if(1==n,0,1+A302031(A302034(n)));

a(1) = 0; for n > 1, a(n) = 1 + a(A302034(n)).
a(n) = A001221(A302026(n)).
a(n) = A069010(A269388(n)).

A302038 Semiludic numbers or "Ludic semiprimes": numbers n for which A302037(n) = 2.

Original entry on oeis.org

4, 6, 9, 10, 14, 15, 19, 22, 26, 27, 31, 34, 35, 39, 46, 50, 55, 58, 59, 63, 65, 73, 74, 75, 82, 86, 94, 95, 99, 101, 103, 106, 113, 122, 133, 134, 135, 142, 145, 147, 154, 155, 163, 166, 167, 171, 178, 182, 185, 187, 194, 203, 205, 214, 219, 230, 238, 242, 243, 245, 253, 254, 255, 262, 263, 269, 271, 279, 286, 293, 298, 299, 311

Offset: 1

Antti Karttunen, Apr 01 2018

nonn

An analog for A001358 based on the Ludic factorization (see A302032).

Antti Karttunen, Table of n, a(n) for n = 1..3953
Index entries for sequences generated by sieves

Cf. A003309, A255127, A302032, A302037.
Cf. A254100 (a subsequence).
Cf. also A001358, A302036.

k=0; for(n=1,512,if(2==A302037(n),k++;print1(n,","))); \\ Other code as in A302037.

A302040 Numbers k such that A078898(k) is a power of 2; an analog for A000961 based on factorization-kind of process involving the sieve of Eratosthenes (A083221).

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 21, 23, 25, 29, 31, 32, 37, 41, 43, 45, 47, 49, 53, 55, 59, 61, 64, 67, 71, 73, 79, 83, 89, 91, 93, 97, 101, 103, 107, 109, 113, 115, 121, 127, 128, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 189, 191, 193, 197, 199, 203, 211, 223, 227, 229, 233, 235, 239, 241, 247, 251, 256, 257

Offset: 1

Antti Karttunen, Apr 02 2018

nonn

Numbers k for which A302041(k) < 2, or equally, for which A302044(k) = 1.
Sequence A250245(A000961(k)) sorted into ascending order, or in other words, numbers k such that A250246(k) is a prime power (in A000961).
Numbers k such that all terms in iteration sequence k, A302042(k), A302042(A302042(k)), A302042(A302042(A302042(k))), ..., have an equal smallest prime factor (A020639) before the sequence settles to 1, in other words, that they all stay on the same row of A083221. This also forces the column position of each (A078898) to be a power of 2 (A000079).

			For k = 21 = 3*7, the smallest prime factor is 3. A302042(21) = 9, and A302042(9) = 3, both (9 and 3) which also have 3 as their smallest prime factor, and after that the sequence settles to 1, as A302042(3) = 1, thus 21 is included in this sequence.
For k = 27 = 3*3*3, the smallest prime factor is 3. However, A302042(27) = 7, thus 27 is not included in this sequence.

Antti Karttunen, Table of n, a(n) for n = 1..6883
Index entries for sequences generated by sieves

Cf. A000961, A078898, A302036, A302041, A302044, A302053.

Cf. A000040, A000079, A001248 (subsequences).

for(n=1,257,if(2>A302041(n),print1(n,","))); \\ Other code as in A302041.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Scheme

Formula

Extensions

A272565 Smallest ludic factor of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Formula

Extensions

A260739 Column index to A255127: a(1) = 1; for n > 1, a(n) = the position at the stage where n is removed in the sieve which produces Ludic numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

Extensions

A254100 Postludic numbers: Second column of Ludic array A255127.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A302034 A028234 analog for a factorization process based on the Ludic sieve (A255127); Discard all instances of the (smallest) Ludic factor A272565(n) from n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A302031 An omega (A001221) analog based on the Ludic sieve (A255127): a(1) = 0; for n > 1, a(n) = 1 + a(A302034(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A302038 Semiludic numbers or "Ludic semiprimes": numbers n for which A302037(n) = 2.

Views

Author

Keywords

Comments

Links

Crossrefs