A181363 -id:A181363 - cp's OEIS frontend

A008578 Prime numbers at the beginning of the 20th century (today 1 is no longer regarded as a prime).

1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271

Offset: 1

N. J. A. Sloane

1 together with the primes; also called the noncomposite numbers.
Also largest sequence of nonnegative integers with the property that the product of 2 or more elements with different indices is never a square. - Ulrich Schimke (ulrschimke(AT)aol.com), Dec 12 2001 [Comment corrected by Farideh Firoozbakht, Aug 03 2014]
Numbers k whose largest divisor <= sqrt(k) equals 1. (See also A161344, A161345, A161424.) - Omar E. Pol, Jul 05 2009
Numbers k such that d(k) <= 2. - Juri-Stepan Gerasimov, Oct 17 2009
Also first column of array in A163280. Also first row of array in A163990. - Omar E. Pol, Oct 24 2009
Possible values of A136548(m) in increasing order, where A136548(m) = the largest numbers h such that A000203(h) <= k (k = 1,2,3,...), where A000203(h) = sum of divisors of h. - Jaroslav Krizek, Mar 01 2010
Where record values of A022404 occur: A086332(n)=A022404(a(n)). - Reinhard Zumkeller, Jun 21 2010
Positive integers that have no divisors other than 1 and itself (the old definition of prime numbers). - Omar E. Pol, Aug 10 2012
Conjecture: the sequence contains exactly those k such that sigma(k) > k*BigOmega(k). - Irina Gerasimova, Jun 08 2013
Note on the Gerasimova conjecture: all terms in the sequence obviously satisfy the inequality, because sigma(p) = 1+p and BigOmega(p) = 1 for primes p, so 1+p > p*1. For composites, the (opposite) inequality is heuristically correct at least up to k <= 4400000. The general proof requires to show that BigOmega(k) is an upper limit of the abundancy sigma(k)/k for composite k. This proof is easy for semiprimes k=p1*p2 in general, where sigma(k)=1+p1+p2+p1*p2 and BigOmega(k)=2 and p1, p2 <= 2. - R. J. Mathar, Jun 12 2013
Numbers k such that phi(k) + sigma(k) = 2k. - Farideh Firoozbakht, Aug 03 2014
isA008578(n) <=> k is prime to n for all k in {1,2,...,n-1}. - Peter Luschny, Jun 05 2017
In 1751 Leonhard Euler wrote: "Having so established this sign S to indicate the sum of the divisors of the number in front of which it is placed, it is clear that, if p indicates a prime number, the value of Sp will be 1 + p, except for the case where p = 1, because then we have S1 = 1, and not S1 = 1 + 1. From this we see that we must exclude unity from the sequence of prime numbers, so that unity, being the start of whole numbers, it is neither prime nor composite." - Omar E. Pol, Oct 12 2021
a(1) = 1; for n >= 2, a(n) is the least unused number that is coprime to all previous terms. - Jianing Song, May 28 2022
A number p is preprime if p = a*b ==> a = 1 or b = 1. This sequence lists the preprimes in the commutative monoid IN \ {0}. - Peter Luschny, Aug 26 2022

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.
Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966. See Table 84 at pp. 214-217.
G. Chrystal, Algebra: An Elementary Textbook. Chelsea Publishing Company, 7th edition, (1964), chap. III.7, p. 38.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 11.
H. D. Huskey, Derrick Henry Lehmer [1905-1991]. IEEE Ann. Hist. Comput. 17 (1995), no. 2, 64-68. Math. Rev. 96b:01035
D. H. Lehmer, The sieve problem for all-purpose computers. Math. Tables and Other Aids to Computation, Math. Tables and Other Aids to Computation, 7, (1953). 6-14. Math. Rev. 14:691e
D. N. Lehmer, "List of Prime Numbers from 1 to 10,006,721", Carnegie Institute, Washington, D.C. 1909.
R. F. Lukes, C. D. Patterson and H. C. Williams, Numerical sieving devices: their history and some applications. Nieuw Arch. Wisk. (4) 13 (1995), no. 1, 113-139. Math. Rev. 96m:11082
H. C. Williams and J. O. Shallit, Factoring integers before computers. Mathematics of Computation 1943-1993: a half-century of computational mathematics (Vancouver, BC, 1993), 481-531, Proc. Sympos. Appl. Math., 48, AMS, Providence, RI, 1994. Math. Rev. 95m:11143

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]
Chris K. Caldwell, Angela Reddick, Yeng Xiong, and Wilfrid Keller, The History of the Primality of One: A Selection of Sources, (a dynamic survey), Journal of Integer Sequences, Vol. 15 (2012), #12.9.8.
C. K. Caldwell and Y. Xiong, What is the smallest prime?, arXiv preprint arXiv:1209.2007 [math.HO], 2012, and J. Int. Seq. 15 (2012) #12.9.6
Leonhard Euler, Découverte d’une loi tout extraordinaire des nombres, par rapport à la somme de leurs diviseurs, in Bibliothèque impartiale, 3, 1751, pp. 10-31. Reprinted in Opera Postuma, 1, 1862, p.76-84. Number 175 in the Eneström index.
G. P. Michon, Is 1 a prime number?
Omar E. Pol, Illustration of initial terms
Omar E. Pol, Illustration of initial terms of A008578, A161344, A161345, A161424
PrimeFan, Arguments for and against the primality of 1
A. Reddick and Y. Xiong, The search for one as a prime number: from ancient Greece to modern times, Electronic Journal of Undergraduate Mathematics, Volume 16, 1 - 13, 2012. - From _N. J. A. Sloane_, Feb 03 2013
J. Todd, Review of Lehmer's tables, Mathematical Tables and Other Aids to Computation, Vol. 11, No. 60, (1957) (on JSTOR.org).
Wikipedia, "Complete" sequence. [Wikipedia calls a sequence "complete" (sic) if every positive integer is a sum of distinct terms. This name is extremely misleading and should be avoided. - _N. J. A. Sloane_, May 20 2023]
Wikipedia, Dirichlet convolution

The main entry for this sequence is A000040.
The complement of A002808.
Cf. A000732 (boustrophedon transform).
Cf. A000010, A000203.
Cf. A023626 (self-convolution).

A008578:=Concatenation([1],Filtered([1..10^5],IsPrime)); # Muniru A Asiru, Sep 07 2017

a008578 n = a008578_list !! (n-1)
a008578_list = 1 : a000040_list
-- Reinhard Zumkeller, Nov 09 2011

[1] cat [n: n in PrimesUpTo(271)];  // Bruno Berselli, Mar 05 2011

A008578 := n->if n=1 then 1 else ithprime(n-1); fi :

Join[ {1}, Table[ Prime[n], {n, 1, 60} ] ]
NestList[ NextPrime, 1, 57] (* Robert G. Wilson v, Jul 21 2015 *)
oldPrimeQ[n_] := AllTrue[Range[n-1], CoprimeQ[#, n]&];
Select[Range[271], oldPrimeQ] (* Jean-François Alcover, Jun 07 2017, after Peter Luschny *)

PARI
```
is(n)=isprime(n)||n==1
```

isA008578 = lambda n: all(gcd(k, n) == 1 for k in (1..n-1))
print([n for n in (1..271) if isA008578(n)]) # Peter Luschny, Jun 07 2017

a(n) = A000040(n-1).
m is in the sequence iff sigma(m) + phi(m) = A065387(m) = 2m. - Farideh Firoozbakht, Jan 27 2005
a(n) = A158611(n+1) for n >= 1. - Jaroslav Krizek, Jun 19 2009
In the following formulas (based on emails from Jaroslav Krizek and R. J. Mathar), the star denotes a Dirichlet convolution between two sequences, and "This" is A008578.
This = A030014 * A008683. (Dirichlet convolution using offset 1 with A030014)
This = A030013 * A000012. (Dirichlet convolution using offset 1 with A030013)
This = A034773 * A007427. (Dirichlet convolution)
This = A034760 * A023900. (Dirichlet convolution)
This = A034762 * A046692. (Dirichlet convolution)
This * A000012 = A030014. (Dirichlet convolution using offset 1 with A030014)
This * A008683 = A030013. (Dirichlet convolution using offset 1 with A030013)
This * A000005 = A034773. (Dirichlet convolution)
This * A000010 = A034760. (Dirichlet convolution)
This * A000203 = A034762. (Dirichlet convolution)
A002033(a(n))=1. - Juri-Stepan Gerasimov, Sep 27 2009
a(n) = A181363((2*n-1)*2^k), k >= 0. - Reinhard Zumkeller, Oct 16 2010
a(n) = A001747(n)/2. - Omar E. Pol, Jan 30 2012
A060448(a(n)) = 1. - Reinhard Zumkeller, Apr 05 2012
A086971(a(n)) = 0. - Reinhard Zumkeller, Dec 14 2012
Sum_{n>=1} x^a(n) = (Sum_{n>=1} (A002815(n)*x^n))*(1-x)^2. - L. Edson Jeffery, Nov 25 2013

A025480 a(2n) = n, a(2n+1) = a(n).

Original entry on oeis.org

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

Offset: 0

David W. Wilson

These are the Grundy values or nim-values for heaps of n beans in the game where you're allowed to take up to half of the beans in a heap. - R. K. Guy, Mar 30 2006. See Levine 2004/2006 for more about this. - N. J. A. Sloane, Aug 14 2016
When n > 0 is written as (2k+1)*2^j then k = a(n-1) and j = A007814(n), so: when n is written as (2k+1)*2^j-1 then k = a(n) and j = A007814(n+1), when n > 1 is written as (2k+1)*2^j+1 then k = a(n-2) and j = A007814(n-1). - Henry Bottomley, Mar 02 2000 [sequence id corrected by Peter Munn, Jun 22 2022]
According to the comment from Deuard Worthen (see Example section), this may be regarded as a triangle where row r=1,2,3,... has length 2^(r-1) and values T(r,2k-1)=T(r-1,k), T(r,2k)=2^(r-1)+k-1; i.e., previous row gives 1st, 3rd, 5th, ... term and 2nd, 4th, ... terms are numbers 2^(r-1),...,2^r-1 (i.e., those following the last one from the previous row). - M. F. Hasler, May 03 2008
Let StB be a Stern-Brocot tree hanging between (pseudo)fractions Left and Right, then StB(1) = mediant(Left,Right) and for n>1: StB(n) = if a(n-1)<>0 and a(n)<>0 then mediant(StB(a(n-1)),StB(a(n))) else if a(n)=0 then mediant(StB(a(n-1)),Right) else mediant(Left,StB(a(n-1))), where mediant(q1,q2) = ((numerator(q1)+numerator(q2)) / (denominator(q1)+denominator(q2))). - Reinhard Zumkeller, Dec 22 2008
This sequence is the unique fixed point of the function (a(0), a(1), a(2), ...) |--> (0, a(0), 1, a(1), 2, a(2), ...) which interleaves the nonnegative integers between the elements of a sequence. - Cale Gibbard (cgibbard(AT)gmail.com), Nov 18 2009
Also the number of remaining survivors in a Josephus problem after the person originally first in line has been eliminated (see A225381). - Marcus Hedbring, May 18 2013
A fractal sequence - see Levine 2004/2006. - N. J. A. Sloane, Aug 14 2016
From David James Sycamore, Apr 29 2020: (Start)
One of a family of fractal sequences, S_k; defined as follows for k >= 2: a(k*n) = n, a(k*n+r) = a((k-1)*n + (r-1)), r = 1..(k-1). S_2 is A025480; S_3 gives: a(3*n) = n, a(3*n + 1) = a(2*n), a(3*n + 2) = a(2*n + 1), which is A263390.
The subsequence of all nonzero terms is A131987. (End)
Similar to but different from A108202. - N. J. A. Sloane, Nov 26 2020
This sequence can be otherwise defined in two alternative (but related) ways, with a(0)=0, as follows: (i) If a(n) is a novel term, then a(n+1) = a(a(n)); if a(n) has been seen before, most recently at a(m), then a(n+1) = n-m (as in A181391). (ii) As above for novel a(n), then if a(n) has been seen before, a(n+1) = smallest k < a(n) which is not already a term. - David James Sycamore, Jul 13 2021
From a binary perspective, the sequence can be seen as even,odd pairs where the odd value is the previous even value, dropping the rightmost bits up to and including the lowest zero bit, aka right-shifted past the lowest clear bit. E.g., (5)101 -> 1, (17)10001 -> (4)100, (29)11101 -> (7)111, (39)100111 -> (2)10. - Joe Nellis, Oct 09 2022

			From Deuard Worthen (deuard(AT)raytheon.com), Jan 27 2006: (Start)
The sequence can be constructed as a triangle as:
  0
  0  1
  0  2  1  3
  0  4  2  5  1  6  3  7
  0  8  4  9  2 10  5 11  1 12  6 13  3 14  7 15
  ...
At each stage we interleave the next 2^m numbers in the previous row. (End)
Left=0/1, Right=1/0: StB=A007305/A047679; Left=0/1, Right=1/1: StB=A007305/A007306; Left=1/3, Right=2/3: StB=A153161/A153162. - _Reinhard Zumkeller_, Dec 22 2008

L. Levine, Fractal sequences and restricted Nim, Ars Combin. 80 (2006), 113-127.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Josef Eschgfäller and Andrea Scarpante, Dichotomic random number generators, arXiv:1603.08500 [math.CO], 2016.
Ralf Hinze, Concrete stream calculus: An extended study, J. Funct. Progr. 20 (5-6) (2010) 463-535, doi, Section 3.2.4.
L. Levine, Fractal sequences and restricted Nim, arXiv:math/0409408 [math.CO], 2004.
Ralf Stephan, Some divide-and-conquer sequences ....
Ralf Stephan, Table of generating functions.
Paul Tarau, A Groupoid of Isomorphic Data Transformations, Calculemus 2009, 8th International Conference, MKM 2009, pp. 170-185, Springer, LNAI 5625.
Index entries for sequences related to the Josephus Problem.

The Y-projection of A075300.

Cf. A108202, A138002, A000265, A003602, A103391, A153733, A220466, A225381, A131987, A263390, A181391, A007814.

import Data.List
interleave xs ys = concat . transpose $ [xs,ys]
a025480 = interleave [0..] a025480
-- Cale Gibbard, Nov 18 2009

Cf. comments by Worthen and Hasler.
import Data.List (transpose)
a025480 n k = a025480_tabf !! n !! k
a025480_row n = a025480_tabf !! n
a025480_tabf = iterate (\xs -> concat $
   transpose [xs, [length xs .. 2 * length xs - 1]]) [0]
a025480_list = concat $ a025480_tabf
-- Reinhard Zumkeller, Apr 29 2012

A025480 := proc(n)
    option remember ;
    if type(n,'even') then
        n/2 ;
    else
        procname((n-1)/2) ;
    end if;
end proc:
seq(A025480(n),n=0..100) ; # R. J. Mathar, Jul 16 2020

a[n_] := a[n] = If[OddQ@n, a[(n - 1)/2], n/2]; Table[ a[n], {n, 0, 83}] (* Robert G. Wilson v, Mar 30 2006 *)
Table[BitShiftRight[n, IntegerExponent[n, 2] + 1], {n, 100}] (* IWABUCHI Yu(u)ki, Oct 13 2012 *)

a(n)={while(n%2,n\=2);n\2} \\ M. F. Hasler, May 03 2008

A025480(n)=n>>valuation(n*2+2,2) \\ M. F. Hasler, Apr 12 2012

def A025480(n): return n>>((~(n+1)&n).bit_length()+1) # Chai Wah Wu, Jul 13 2022

A025480 = lambda n: odd_part(n+1)//2
[A025480(n) for n in (0..83)] # Peter Luschny, May 20 2014

a(n) = A003602(n+1) - 1. [Corrected by Max Alekseyev, May 05 2022]
a(n) = (A000265(n+1)-1)/2 = ((n+1)/A006519(n+1)-1)/2.
a(n) = A153733(n)/2. - Reinhard Zumkeller, Dec 31 2008
2^A007814(n+1)*(2*a(n)+1) = n+1. (See functions hd, tl and cons in [Paul Tarau 2009].) - Paul Tarau (paul.tarau(AT)gmail.com), Mar 21 2010
a(3*n + 1) = A173732(n). - Reinhard Zumkeller, Apr 29 2012
a((2*n+1)*2^p-1) = n, p >= 0 and n >= 0. - Johannes W. Meijer, Jan 24 2013
a(n) = n - A225381(n). - Marcus Hedbring, May 18 2013
G.f.: -1/(1-x) + Sum_{k>=0} x^(2^k-1)/(1-2*x^2^(k+1)+x^2^(k+2)). - Ralf Stephan, May 19 2013
a(n) = A049084(A181363(n+1)). - Reinhard Zumkeller, Mar 22 2014
a(n) = floor(n / 2^A001511(n+1)). - Adam Shelly, Mar 05 2019
Recursion: a(0) = 0; a(n + 1) = a(a(n)) if a(n) is a first occurrence of a term, else a(n + 1) = n - a(n-1). - David James Sycamore, Apr 29 2020
a(n) * 2^(A007814(n+1)+1) + 2^A007814(n+1) - 1 = n (equivalent to the formula given in the comment by Paul Tarau). - Ruud H.G. van Tol, Apr 14 2023
Sum_{k=1..n} a(k) = n^2/6 + O(n). - Amiram Eldar, Aug 07 2023

Edited by M. F. Hasler, Mar 16 2018

A051438 a(n) = prime(2^n - 1).

Original entry on oeis.org

2, 5, 17, 47, 127, 307, 709, 1613, 3659, 8147, 17851, 38867, 84011, 180497, 386083, 821603, 1742527, 3681113, 7754017, 16290041, 34136021, 71378551, 148948133, 310248233, 645155191, 1339484149, 2777105117, 5750079043, 11891268397, 24563311217, 50685770143

Offset: 1

N. J. A. Sloane

nonn

Amiram Eldar, Table of n, a(n) for n = 1..78 (calculated using the b-file at A033844; terms 1..57 from Hugo Pfoertner)

Cf. A000040, A000225, A033844, A018249, A051440, A051439, A151799.

Prime[2^Range[34] - 1] (* Vladimir Joseph Stephan Orlovsky, Jul 19 2011 *)

a(n)=prime(2^n-1) \\ Charles R Greathouse IV, Sep 28 2015

a(n) = A181363(2^n - 1). - Reinhard Zumkeller, Oct 16 2010
a(n) = A000040(A000225(n)). - Michel Marcus, Nov 28 2017
a(n) = A151799(A033844(n)). - Amiram Eldar, Jun 30 2024

More terms from Michael Lugo (mlugo(AT)thelabelguy.com), Dec 22 1999

A337821 For n >= 0, a(4n+1) = 0, a(4n+3) = a(2n+1) + 1, a(2n+2) = a(n+1).

Original entry on oeis.org

0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 0, 2, 3, 0, 0, 0, 1, 0, 0, 1, 2, 1, 0, 0, 1, 2, 0, 3, 4, 0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 0, 2, 3, 1, 0, 0, 1, 0, 0, 1, 2, 2, 0, 0, 1, 3, 0, 4, 5, 0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 0, 2, 3, 0, 0, 0, 1, 0, 0, 1, 2, 1, 0, 0, 1, 2, 0, 3, 4, 1

Offset: 1

Peter Munn, Sep 23 2020

This sequence is the ruler sequence A007814 interleaved with this sequence; specifically, the odd bisection is A007814, the even bisection is the sequence itself.
The 3-adic valuation of the Doudna sequence (A005940).
The 2-adic valuation of Kimberling's paraphrase (A003602) of the binary number system. [Edited Peter Munn, Aug 13 2025.]

			Start of table showing the interleaving with ruler sequence, A007814:
   n  a(n)  A007814    a(n/2)
            ((n+1)/2)
   1   0       0
   2   0                 0
   3   1       1
   4   0                 0
   5   0       0
   6   1                 1
   7   2       2
   8   0                 0
   9   0       0
  10   0                 0
  11   1       1
  12   1                 1
  13   0       0
  14   2                 2
  15   3       3
  16   0                 0
  17   0       0
  18   0                 0
  19   1       1
  20   0                 0
  21   0       0
  22   1                 1
  23   2       2
  24   1                 1

Odd bisection: A007814.
A000265, A003602, A005940, A007949 are used in a formula defining this sequence.
Positions of zeros: A091072.
Sequences with similar interleaving: A089309, A014577, A025480, A034947, A038189, A082392, A099545, A181363, A274139.

a[n_] := IntegerExponent[(n/2^IntegerExponent[n, 2] + 1)/2, 2]; Array[a, 100] (* Amiram Eldar, Sep 30 2020 *)

a(n) = valuation(n>>valuation(n,2)+1, 2) - 1; \\ Kevin Ryde, Apr 06 2024

a(2*n) = a(n).
a(2*n+1) = A007814(n+1).
a(n) = A007949(A005940(n)).
a(n) = A007814(A003602(n)) = A007814((A000265(n)+1) / 2) = A089309(n) - 1.
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1. - Amiram Eldar, Sep 13 2024

cp's OEIS Frontend

A008578 Prime numbers at the beginning of the 20th century (today 1 is no longer regarded as a prime).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

A025480 a(2n) = n, a(2n+1) = a(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Haskell

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

Extensions

A051438 a(n) = prime(2^n - 1).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A337821 For n >= 0, a(4n+1) = 0, a(4n+3) = a(2n+1) + 1, a(2n+2) = a(n+1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula