A008364 11-rough numbers: not divisible by 2, 3, 5 or 7.

1, 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, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209, 211, 221, 223, 227, 229, 233, 239, 241, 247

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

The first A005867(4) = 48 terms give the reduced residue system for the 4th primorial number 210 = A002110(4).

This sequence is closed under multiplication: any product of terms is also a term. - Labos Elemer, Feb 26 2003

Conjecture: these are numbers n such that (Sum_{k=1..n} k^4) mod n = 0 and (Sum_{k=1..n} k^6) mod n = 0. - Gary Detlefs, Dec 20 2011

From Peter Bala, May 03 2018: (Start)

The above conjecture is true. Let m be even and let the m-th Bernoulli number be written in reduced form as Bernoulli(m) = N(m)/D(m). Apply Ireland and Rosen, Proposition 15.2.2, to show the congruence D(m)*( Sum_{k = 1..n} k^m )/n = N(m) (mod n) holds for all n >= 1. It follows easily from this congruence that ( Sum_{k = 1..n} k^m )/n is integral iff n is coprime to D(m). Now Bernoulli(4) = -1/(2*3*5) and Bernoulli(6) = 1/(2*3*7) so the numbers n such that both (Sum_{k=1..n} k^4) mod n = 0 and (Sum_{k=1..n} k^6) mod n = 0 are exactly those numbers coprime to the primes 2, 3, 5 and 7, that is, the 11-rough numbers. (End)

Conjecture: these are numbers n such that (n^6 mod 210 = 1) or (n^6 mod 210 = 169). - Gary Detlefs, Dec 30 2011

The second Detlefs conjecture above is true and extremely easy to verify with some basic properties of congruences: take the terms of this sequence up to 209 and compute their sixth powers modulo 210: there should only be 1's and 169's there. Then take the complement of this sequence up to 210, where you will see no instances of 1 or 169. - Alonso del Arte, Jan 12 2014

It is well-known that the product of 7 consecutive integers is divisible by 7!. Conjecture: This sequence is exactly the set of positive values of r such that ( Product_{k = 0..6} n + k*r )/7! is an integer for all n. - Peter Bala, Nov 14 2015

From Ruediger Jehn, Nov 05 2020: (Start)

This conjecture is true. The first part of the proof deals with numbers not in A008364, i.e., numbers which are divisible by p (p either 2, 3, 5, 7). Let r = p*s and n = 1, then (Product_{k = 0..6} n + k*r) is not divisible by p, because none of the factors 1 + k*p*s are divisible by p. Hence dividing the product by 7! does not return an integer.

The second part deals with numbers in A008364. If r and q are coprime, then for any i < q there exists k < q with (k*r mod q) = i. From this, it also follows that for any n there exists k < q with ((n + k*r) mod q) = 0. But this means that Product_{k = 0..6} n + k*r is divisible by all numbers from 2 to 7 because there is always a factor that is divisible. We still have to show that the product is also divisible by 2 times 3 times 4 times 6. If the k_1 with ((n + k_1*r) mod 4) = 0 is even, then (n mod 2) = ((n + 2*r) mod 2) = ((n + 4*r) mod 2) = ((n + 6*r) mod 2) = 0. If this k_1 is odd, then ((n + r) mod 2) = ((n + 3*r) mod 2) = ((n + 5*r) mod 2) = 0. In both cases there are at least 2 other factors divisible by 2. If the k_2 with ((n + k_2*r) mod 6) = 0 is smaller than 4, then ((n + (k_2 + 3)*r) mod 3) = 0. Otherwise, ((n + (k_2 - 3)*r) mod 3) = 0. In both cases there is at least 1 other factor divisible by 3. And therefore Product_{k = 0..6} n + k*r is divisible by 7! for any n.

(End)

References

• Diatomic sequence of 4th prime: A. de Polignac (1849), J. Dechamps (1907).
• Dickson L. E., History of the Theory of Numbers, Vol. 1, p. 439, Chelsea, 1952.
• K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer-Verlag, 1980.

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Alphonse de Polignac, Recherches Nouvelles sur les Nombres Premiers, in Comptes Rendus de l'Académie des Sciences, October 15 1849. See also Rectification.
• Alphonse de Polignac, Six propositions arithmologiques déduites du crible d'Ératosthène, Nouvelles annales de mathématiques : journal des candidats aux écoles polytechnique et normale, Série 1, Tome 8 (1849), pp. 423-429.
• Han-Lin Li, Shu-Cherng Fang, and Way Kuo, The Periodic Table of Primes, Advances in Pure Mathematics, Volume 14, Issue 5, May 2024.
• Eric Weisstein's World of Mathematics, Rough Number
• Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,-1).
• Index entries for sequences related to smooth numbers

Crossrefs

First differences give A049296. Cf. A002110, A048597.

For k-rough numbers with other values of k, see A000027, A005408, A007310, A007775, A008364, A008365, A008366, A166061, A166063. - Michael B. Porter, Oct 10 2009

Cf. A005867, A092695, A210679, A080672 (complement).

Programs

Haskell

a008364 n = a008364_list !! (n-1)
a008364_list = 1 : filter ((> 7) . a020639) [1..]
-- Reinhard Zumkeller, Mar 26 2012

Maple

for i from 1 to 500 do if gcd(i,210) = 1 then print(i); fi; od;
t1:=[]; for i from 1 to 1000 do if gcd(i,210) = 1 then t1:=[op(t1),i]; fi; od: t1;
S:= (j,n)-> sum(k^j,k=1..n): for n from 1 to 247 do if (S(4,n) mod n = 0) and (S(6,n) mod n = 0) then print(n) fi od; # Gary Detlefs, Dec 20 2011

Mathematica

Select[ Range[ 300 ], GCD[ #1, 210 ] == 1 & ]
Select[Range[250], Mod[#, 2]>0 && Mod[#, 3]>0 && Mod[#, 5]>0 && Mod[#, 7]>0 &] (* Vincenzo Librandi, Nov 16 2015 *)
Cases[Range@1000, x_ /; NoneTrue[Array[Prime, 4], Divisible[x, #] &]] (* Mikk Heidemaa, Dec 07 2017 *)
Select[Range[250],Union[Divisible[#,{2,3,5,7}]]=={False}&] (* Harvey P. Dale, Sep 24 2021 *)

PARI

isA008364(n) = gcd(n,210)==1 \\ Michael B. Porter, Oct 10 2009

Formula

Starting with a(49) = 211, a(n) = a(n-48) + 210. - Zak Seidov, Apr 11 2011

a(n) = a(n-1) + a(n-48) - a(n-49). - Charles R Greathouse IV, Dec 21 2011

A020639(a(n)) > 7. - Reinhard Zumkeller, Mar 26 2012

G.f.: x*(x^48 + 10*x^47 + 2*x^46 + 4*x^45 + 2*x^44 + 4*x^43 + 6*x^42 + 2*x^41 + 6*x^40 + 4*x^39 + 2*x^38 + 4*x^37 + 6*x^36 + 6*x^35 + 2*x^34 + 6*x^33 + 4*x^32 + 2*x^31 + 6*x^30 + 4*x^29 + 6*x^28 + 8*x^27 + 4*x^26 + 2*x^25 + 4*x^24 + 2*x^23 + 4*x^22 + 8*x^21 + 6*x^20 + 4*x^19 + 6*x^18 + 2*x^17 + 4*x^16 + 6*x^15 + 2*x^14 + 6*x^13 + 6*x^12 + 4*x^11 + 2*x^10 + 4*x^9 + 6*x^8 + 2*x^7 + 6*x^6 + 4*x^5 + 2*x^4 + 4*x^3 + 2*x^2 + 10*x + 1) / (x^49 - x^48 - x + 1). - Colin Barker, Sep 27 2013

a(n) = 35*n/8 + O(1). - Charles R Greathouse IV, Sep 14 2015

A007775 INTERSECT A206547. - R. J. Mathar, Apr 10 2024

Extensions

New name from Charles R Greathouse IV, Dec 21 2011 based on comment from Michael B. Porter, Oct 10 2009