Search: a070971 -id:a070971
|
| |
| |
|
|
|
3, 4, 15, 6, 105, 30, 1155, 770, 36465, 210, 15015, 6006
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
LINKS
|
|
|
|
KEYWORD
|
dead
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A048669
|
|
The Jacobsthal function g(n): maximal gap in a list of all the integers relatively prime to n.
|
|
+10
17
|
|
|
|
1, 2, 2, 2, 2, 4, 2, 2, 2, 4, 2, 4, 2, 4, 3, 2, 2, 4, 2, 4, 3, 4, 2, 4, 2, 4, 2, 4, 2, 6, 2, 2, 3, 4, 3, 4, 2, 4, 3, 4, 2, 6, 2, 4, 3, 4, 2, 4, 2, 4, 3, 4, 2, 4, 3, 4, 3, 4, 2, 6, 2, 4, 3, 2, 3, 6, 2, 4, 3, 6, 2, 4, 2, 4, 3, 4, 3, 6, 2, 4, 2, 4, 2, 6, 3, 4, 3, 4, 2, 6, 3, 4, 3, 4, 3, 4, 2, 4, 3, 4, 2, 6, 2, 4, 5
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Equivalently, g(n) is the least integer such that among any g(n) consecutive integers i, i+1, ..., i+g(n)-1 there is at least one which is relatively prime to n.
The definition refers to all integers, not just those in the range 1..n-1.
Jacobsthal's function is used in the proofs of Recamán's and Pomerance's conjectures on P-integers--see A192224. - Jonathan Sondow, Jun 14 2014
|
|
|
REFERENCES
|
E. Jacobsthal, Uber Sequenzen ganzer Zahlen, von denen keine zu n teilerfremd ist, I, II, III. Norske Vid. Selsk. Forh., 33, 1960, 117-139.
D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Pages 33-34.
E. Westzynthius, Uber die Verteilung der Zahlen, die zu der n ersten Primzahlen teilerfremd sind, Comm. Phys. Math. Helsingfors 25 (1931), 1-37.
|
|
|
LINKS
|
|
|
|
FORMULA
|
g(n) = g(Rad(n)) (cf. A007947). So in studying g(n) we may focus on the case when n is a product of w (say) distinct primes.
g(n) <= 2^w for all w [Kanold].
g(n) <= 2^(1/w) for all w >= e^50 [Kanold].
For some unknown X, g(n) <= X*(w*log(w))^2 for all w [Iwaniec].
(End)
|
|
|
EXAMPLE
|
g(6)=4 because the gap between 1 and 5, both being relatively prime to 6, is maximal and 5-1 = 4.
g(7)=2, because the numbers relatively prime to 7 are 1,2,3,4,5,6,8,9,10,..., and the biggest gap is 2. Similarly a(p) = 2 for any prime p. - N. J. A. Sloane, Sep 08 2012
|
|
|
MATHEMATICA
|
g[n_] := Module[{L = 1, m = 1}, For[k = 2, k <= n+1, k++, If[GCD[k, n] == 1, If[L+m < k, m = k-L]; L = k]]; m]; Table[g[n], {n, 1, 105}] (* Jean-François Alcover, Sep 03 2013, after M. F. Hasler *)
Table[Max[Differences[Select[Range[110], CoprimeQ[#, n]&]]], {n, 110}] (* Harvey P. Dale, Jan 10 2022 *)
|
|
|
PROG
|
(PARI) A048669(n)=my(L=1, m=1); for(k=2, n+1, gcd(k, n)>1 && next; L+m<k && m=k-L; L=k); m \\ M. F. Hasler, Sep 08 2012
(Haskell)
a048669 n = maximum $ zipWith (-) (tail ts) ts where
ts = a038566_row n ++ [n + 1]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Edited, changed symbol to g(n), added references pertaining to bounds. - N. J. A. Sloane, Apr 19 2017
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A076366
|
|
Number of numbers for which the count of nonprimes (i.e., 1 and composites) in their reduced residue set equals n.
|
|
+10
4
|
|
|
|
10, 6, 6, 4, 4, 7, 3, 4, 3, 7, 4, 4, 0, 6, 5, 1, 4, 3, 7, 4, 7, 2, 3, 3, 2, 2, 6, 5, 2, 2, 0, 6, 4, 3, 5, 4, 5, 3, 1, 3, 3, 4, 4, 6, 2, 3, 1, 6, 1, 6, 3, 6, 1, 4, 4, 4, 1, 1, 3, 6, 3, 2, 4, 4, 1, 1, 2, 4, 6, 0, 3, 4, 3, 5, 4, 1, 2, 8, 2, 5, 6, 2, 2, 5, 1, 4, 2, 4, 7, 2, 1, 2, 6, 1, 3, 5, 2, 3, 5, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = Card{x; A048864(x) = n}; a(n)=0 if supposedly no such number exists (see A072023).
|
|
|
EXAMPLE
|
A048864(x) = 13: S = {}, a(13) = 0;
A048864(x) = 16: S = {144}, a(16) = 1;
A048864(x) = 22: S = {57,92}, a(22) = 2;
A048864(x) = 7: S = {13,34,50}, a(7) = 3;
A048864(x) = 4: S = {15,22,54,84}, a(4) = 4;
A048864(x) = 15: S = {35,64,68,156,240}, a(15) = 5;
A048864(x) = 2: S = {5,10,14,20,42,60}, a(2) = 6;
A048864(x) = 6: S = {11,21,32,40,72,78,210}, a(6) = 7;
A048864(x) = 78: S = {133,177,268,440,490,552,870,990}, a(78) = 8;
A048864(x) = 1: S = {1,2,3,4,6,8,12,18,24,30}, a(1) = 10; See A048597.
|
|
|
PROG
|
(PARI) listn(nn) = {my(v = vector(10^5, n, eulerphi(n) - (primepi(n) - omega(n)))); vector(nn, k, if (#(w=Vec(select(x->(x==k), v, 1))) == 0, 0, #w)); } \\ Michel Marcus, Feb 23 2020
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A128759
|
|
Least k such that the Jacobsthal function A048669(k) = n.
|
|
+10
1
|
|
|
|
1, 2, 15, 6, 105, 30, 1155, 770, 36465, 210, 15015, 6006, 255255, 2310, 8580495, 102102, 4849845, 72930, 20056049013, 74364290, 5898837945, 30030, 3234846615, 881790, 195282582495, 510510, 218257003965, 20281170, 100280245065, 17160990, 934482952262145, 6614136163635
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Except for a(1) and a(2), the same as A070971. It appears that a(2n)=2a(n) for odd n. Because the primorial numbers (A002110) yield record values of the Jacobsthal function, we have a(A048670(n))=A002110(n). Note that numbers in this sequence up to n=18 have the form p#, p#/2, p#/q, or p#/(2q), where p and q are primes with 2<q<p and p# denotes the product of the primes up to p.
|
|
|
LINKS
|
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.005 seconds
|
