A054403 -id:A054403 - cp's OEIS frontend

A007775 Numbers not divisible by 2, 3 or 5.

1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97, 101, 103, 107, 109, 113, 119, 121, 127, 131, 133, 137, 139, 143, 149, 151, 157, 161, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 203, 209

Offset: 1

N. J. A. Sloane

Also numbers n such that the sum of the 4th powers of the first n positive integers is divisible by n, or A000538(n) = n*(n+1)(2*n+1)(3*n^2+3*n-1)/30 is divisible by n. - Alexander Adamchuk, Jan 04 2007
Also the 7-rough numbers: positive integers that have no prime factors less than 7. - Michael B. Porter, Oct 09 2009
a(n) mod 3 has period 8, repeating [1,1,2,1,2,1,2,2] = (n mod 2) + floor(((n-1) mod 8)/7) - floor(((n-2) mod 8)/7) + 1. floor(a(n)/3) is the set of numbers k such that k is congruent to {0,2,3,4,5,6,7,9} mod 10 = floor((5*n-2)/4)-floor((n mod 8)/6). - Gary Detlefs, Jan 08 2012
Numbers k such that C(k+3,3)==1 (mod k) and C(k+5,5)==1 (mod k). - Gary Detlefs, Sep 15 2013
a(n) mod 30 has period 8 repeating [1, 7, 11, 13, 17, 19, 23, 29]. The mean of these 8 numbers is 120/8 = 15. (a(n)-15) mod 30 has period 8 repeating [-14, -8, -4, -2, 2, 4, 8, 14]. One half of the absolute value produces the symmetric sequence [7, 4, 2, 1, 1, 2, 4, 7] = A061501(((n-1) + 16) mod 8). - Gary Detlefs, Sep 24 2013
a(n) are exactly those positive integers m such that the sequence b(n) = n*(n + m)*(n + 2*m)*(n + 3*m)(n + 4*m)/120 is integral. Cf. A007310. - Peter Bala, Nov 13 2015
The asymptotic density of this sequence is 4/15. - Amiram Eldar, Sep 30 2020
If a(n) + a(n+1) = 0 (mod 30), then a(n-j) + a(n+j+1) = a(n) + a(n+1) for each j in [1, n-1]. - Alexandre Herrera, Jun 27 2023

N. J. A. Sloane, Table of n, a(n) for n = 1..8000
Peter Bala, A note on A007775.
Abel Jansma, E_8 Symmetry Structures in the Ising model, Master's thesis, University of Amsterdam, 2018.
Eric Weisstein's World of Mathematics, Rough Number.
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,1,-1).
Index entries for sequences related to smooth numbers

Cf. A000538, A054403, A145011 (first differences).
For k-rough numbers with other values of k, see A000027, A005408, A007310, A007775, A008364, A008365, A008366, A166061, A166063.
Complement is A080671.
For digital root of Fibonacci numbers indexed by this sequence, see A227896.

a007775 n = a007775_list !! (n-1)
a007775_list = 1 : filter ((> 5) . a020639) [1..]
-- Reinhard Zumkeller, Jan 06 2013

I:=[1, 7, 11, 13, 17, 19, 23, 29, 31]; [n le 9 select I[n] else Self(n-1) +Self(n-8) - Self(n-9): n in [1..80]]; // G. C. Greubel, Oct 22 2018

for i from 1 to 500 do if gcd(i,30) = 1 then print(i); fi; od;
for k from 1 to 300 do if ((k^2 mod 48=1) or (k^2 mod 48=25)) and ((k^2 mod 120=1) or (k^2 mod 120=49)) then print(k) fi od. # Gary Detlefs, Dec 30 2011

Select[ Range[ 300 ], GCD[ #1, 30 ]==1& ]
Select[Range[250], Mod[#, 2]>0&&Mod[#, 3]>0&&Mod[#, 5]>0&] (* Vincenzo Librandi, Feb 08 2014 *)
a[ n_] := Quotient[ n, 8, 1] 30 + {1, 7, 11, 13, 17, 19, 23, 29}[[Mod[n, 8, 1]]]; (* Michael Somos, Jun 02 2014 *)
LinearRecurrence[{1, 0, 0, 0, 0, 0, 0, 1, -1}, {1, 7, 11, 13, 17, 19, 23, 29, 31}, 100] (* Mikk Heidemaa, Dec 07 2017 *)
Cases[Range@1000, x_ /; NoneTrue[Array[Prime, 3], Divisible[x, #] &]] (* Mikk Heidemaa, Dec 07 2017 *)
CoefficientList[ Series[(x^8 + 6x^7 + 4x^6 + 2x^5 + 4x^4 + 2x^3 + 4x^2 + 6x + 1)/((x - 1)^2 (x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)), {x, 0, 55}], x] (* Robert G. Wilson v, Dec 07 2017 *)

isA007775(n) = gcd(n,30)==1 \\ Michael B. Porter, Oct 09 2009

{a(n) = n\8 * 30 + [ -1, 1, 7, 11, 13, 17, 19, 23][n%8 + 1]} /* Michael Somos, Feb 05 2011 */

{a(n) = n\8 * 6 + 9 + 3 * (n+1)\2 * 2 - max(5, (n-2)%8) * 2} /* Michael Somos, Jun 02 2014 */

Vec(x*(1+6*x+4*x^2+2*x^3+4*x^4+2*x^5+4*x^6+6*x^7+x^8)/((1+x)*(x^2+1)*(x^4+1)*( x-1)^2) + O(x^100)) \\ Altug Alkan, Nov 16 2015

def A007775(n): return ((m:=n-1)<<2|1)-(m>>2&-2)+(2,0,-2,0)[m-1>>1&3] # Chai Wah Wu, Feb 02 2025

a = lambda n: ((((n-1)<< 2)-((n-1)>>2))|1) + ((((n-1)<<1)-((n-1)>> 1)) & 2)
print([a(n) for n in (1..56)]) # after Andrew Lelechenko, Peter Luschny, Jul 08 2017

A141256(a(n)) = n+1. - Reinhard Zumkeller, Jun 17 2008
From R. J. Mathar, Feb 27 2009: (Start)
a(n+8) = a(n) + 30.
a(n) = a(n-1) + a(n-8) - a(n-9).
G.f.: x*(1 + 6*x + 4*x^2 + 2*x^3 + 4*x^4 + 2*x^5 + 4*x^6 + 6*x^7 + x^8)/((1 + x)*(x^2 + 1)*(x^4 + 1)*(x-1)^2). (End)
a(n) = 4*n - 3 - 2*floor((n-1)/8) + (1 + (-1)^floor((n-2)/2))*(-1)^floor((n-2)/4), n >= 1. - Timothy Hopper, Mar 14 2010
a(1 - n) = -a(n). - Michael Somos, Feb 05 2011
Numbers k such that ((k^2 mod 48=1) or (k^2 mod 48=25)) and ((k^2 mod 120=1) or (k^2 mod 120=49)). - Gary Detlefs, Dec 30 2011
Numbers k such that k^2 mod 30 is 1 or 19. - Gary Detlefs, Dec 31 2011
a(n) = 3*(floor((5*n-2)/4) - floor((n mod 8)/6)) + (n mod 2) + floor(((n-1) mod 8)/7) - floor(((n-2) mod 8)/7) + 1. - Gary Detlefs, Jan 08 2012
a(n) = 4*n - 3 + 2*(floor((n+6)/8) - floor((n+4)/8) - floor((n+2)/8) + floor(n/8) - floor((n-1)/8)), n >= 1. From the o.g.f. given above by R. J. Mathar (with the denominator written as (1-x^8)*(1-x)), and a two-step reduction of the floor functions. Compare with Hopper's and Detlefs's formulas above. - Wolfdieter Lang, Jan 26 2012
a(n) = (6*f(n) - 3 + (-1)^f(n))/2, where f(n)= n + floor(n/4)+ floor(((n+4) mod 8)/6). - Gary Detlefs, Sep 15 2013
a(n) = 30*floor((n-1)/8) + 15 + 2*f((n-1) mod 8 + 16)*(-1)^floor(((n+3) mod 8)/4), where f(n) = (n*(n+1)/2+1) mod 10. - Gary Detlefs, Sep 24 2013
a(n) = 3*n + 6*floor(n/8) + (n mod 2) - 2*floor(((n-2) mod 8)/6) - 2*floor(((n-2) mod 8)/7) + 1. - Gary Detlefs, Jun 01 2014
a(n+1) = ((n << 2 - n >> 2) || 1) + ((n << 1 - n >> 1) && 2), where << and >> are bitwise left and right shifts, || and && are bitwise "or" and "and". - Andrew Lelechenko, Jul 08 2017
a(n) = 2*n + 2*floor(1/2 + (7*n)/8) + 2*(91 mod (2 - ((3*n)/4 + n^2/4) mod 2)) - 3 (n > 0). - Mikk Heidemaa, Dec 06 2017
Sum_{n>=1} (-1)^(n+1)/a(n) = sqrt(23 + sqrt(5) - sqrt(6*(5 + sqrt(5))))*Pi/15. - Amiram Eldar, Dec 13 2021

A055399 Number of stages of sieve of Eratosthenes needed to identify n as prime or composite.

Original entry on oeis.org

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

Offset: 3

Henry Bottomley, May 15 2000

Primes are known as primes actually one step before a(n): at step k of the sieve, multiples of prime(k) are removed, the smallest integer removed being prime(k)^2; every remaining integer less than prime(k+1)^2 will then never be removed, and it is newly known at step k for those between prime(k)^2 and prime(k+1)^2. For example, at step 3, multiples of prime(3) = 5 are removed and remaining integers after this step are prime up to prime(4)^2 = 49; then, 29, 31, 37, 41, 43, 47 are known as prime at step 3. - Jean-Christophe Hervé, Nov 01 2013

			a(7)=2 because 7 is not removed by the first two stages of the sieve, but is less than the square of the second prime (though not the square of the first); a(35)=3 because 35 is removed in the third stage as a multiple of 5.

T. D. Noe, Table of n, a(n) for n = 3..10000
H. B. Meyer, Eratosthenes' sieve
J. Britton, Sieve of Eratosthenes Applet
C. K. Caldwell, The Prime Glossary, Sieve of Eratosthenes
Wikipedia, Sieve of Eratosthenes

Cf. A000040, A002808, A004280, A038179, A055396, A054403, A055398, A083269, A010051, A056811.

a[n_ /; !PrimeQ[n]] := PrimePi[ FactorInteger[n][[1, 1]]]; a[n_ /; PrimeQ[n]] := PrimePi[ NextPrime[ Sqrt[n]]]; Table[a[n], {n, 3, 107}](* Jean-François Alcover, Jun 11 2012, after formula *)

If n is composite, a(n) = A055396(n); if n is prime, a(n) = A056811(n)+1. [Corrected by Charles R Greathouse IV, Sep 03 2013]

a(n) = A010051(n)*(A056811(n)+1)+(1-A010051(n))*A055396(n). - Jean-Christophe Hervé, Nov 01 2013

A230773 Minimum number of steps in an alternate definition of the Sieve of Eratosthenes needed to identify n as prime or composite.

Original entry on oeis.org

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

Offset: 1

Jean-Christophe Hervé, Oct 30 2013

This sequence differs from A055399 on prime numbers; as they are never removed during the sieve, it is partly a matter of convention to decide at which step they are classified as prime. Because the smallest integer to be removed at step k is prime(k)^2, integers between prime(k)^2 and prime(k+1)^2 and not removed after step k are known as prime after this step.

This is how this sequence is defined for noncomposite numbers (primes and 1): for any noncomposite number n between prime(k)^2 and prime(k+1)^2, a(n) = k. An exception is made for 3 to fit the usual presentation of the sieve, according to which 3 is classified as prime after the first step, that is, a(3) = 1 (it can be argued, though, that running the first step of the sieve is not actually necessary to identify 3 as prime because 3 < prime(1)^2: see the comment on A000040 by Daniel Forgues, referring to 2 and 3 as "forcibly prime" since there are no integers greater than 1 and less than or equal to their respective square roots).

			By convention, a(1)=a(2)=0, as 1 is not involved in the sieve, and 2 is known as prime before the first step (first integer > 1).
At step 1, multiples of 2 are removed, beginning with 4 = 2*2; 5 and 7 are not removed and cannot be removed at any further step because they are less than 3*3 = 9; therefore, integers from 4 to 8 are all classified as prime or not prime after the first step: a(4) = a(5) = a(6) = a(7) = a(8) = 1.
At step 2, all integers < 5^2 = 25 will be classified because those >= 9 and not already classified at step one are either multiple of 3 or prime; therefore, for 9 <= n < 25, a(n) = 1 if n is even, a(n) = 2 if n is odd.

Jean-Christophe Hervé, Table of n, a(n) for n = 1..10000
C. K. Caldwell, The Prime Glossary, Sieve of Eratosthenes
H. B. Meyer, Eratosthenes' sieve
F. Richman, Generating primes by the sieve of Eratosthenes
Wikipedia, Sieve of Eratosthenes

Cf. A000040, A002808, A004280, A010051, A038179, A054403, A055396, A055398, A055399, A056811, A083269.

a(n) = A010051(n)*(A056811(n) + mod(n^2,3))+(1-A010051(n))*A055396(n)
(that is, if n is prime > 3, a(n) = primepi(firstprimebelow(sqrt(n)); else if n is composite, a(n) = A055396(n)).
a(n) = A055399(n) - A010051(n)*mod(n^2,3).

cp's OEIS Frontend

A007775 Numbers not divisible by 2, 3 or 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Sage

Formula

A055399 Number of stages of sieve of Eratosthenes needed to identify n as prime or composite.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A230773 Minimum number of steps in an alternate definition of the Sieve of Eratosthenes needed to identify n as prime or composite.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula