|
|
A064413
|
|
EKG sequence (or ECG sequence): a(1) = 1; a(2) = 2; for n > 2, a(n) = smallest number not already used which shares a factor with a(n-1).
|
|
342
|
|
|
1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16, 20, 22, 11, 33, 27, 30, 25, 35, 28, 26, 13, 39, 36, 32, 34, 17, 51, 42, 38, 19, 57, 45, 40, 44, 46, 23, 69, 48, 50, 52, 54, 56, 49, 63, 60, 55, 65, 70, 58, 29, 87, 66, 62, 31, 93, 72, 64, 68, 74, 37, 111, 75, 78, 76, 80, 82
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Locally, the graph looks like an EKG (American English) or ECG (British English).
Theorem: (1) Every number appears exactly once: this is a permutation of the positive numbers. - J. C. Lagarias, E. M. Rains, N. J. A. Sloane, Oct 03 2001
The permutation has cycles (1) (2) (3, 4, 6, 9, 10, 5) (..., 20, 18, 12, 7, 14, 13, 28, 26, ...) (8) ...
Theorem: (2) The primes appear in increasing order. - J. C. Lagarias, E. M. Rains, N. J. A. Sloane, Oct 03 2001
Theorem: (3) When an odd prime p appears it is immediately preceded by 2p and followed by 3p. - Conjectured by Lagarias-Rains-Sloane, proved by Hofman-Pilipczuk.
Theorem: (4) Let a'(n) be the same sequence but with all terms p and 3p (p prime) changed to 2p (see A256417). Then lim a'(n)/n = 1, i.e., a(n) ~ n except for the values p and 3p for p prime. - Conjectured by Lagarias-Rains-Sloane, proved by Hofman-Pilipczuk.
Conjecture: If a(n) != p, then almost everywhere a(n) > n. - Thomas Ordowski, Jan 23 2009
Conjecture: lim #(a_n > n) / n = 1, i.e., #(a_n > n) ~ n. - Thomas Ordowski, Jan 23 2009
Conjecture: A term p^2, p a prime, is immediately preceded by p*(p+1) and followed by p*(p+2). - Vladimir Baltic, Oct 03 2001. This is false, for example the sequence contains the 3 terms p*(p+2), p^2, p*(p+3) for p = 157. - Eric Rains
Theorem: If a(k) = 3p, then |{a(m) : a(m>k) < 3p}| = 3p - k. Proof: If a(k) = 3p, then all a(m<k) < 3p, all a(m>k) > p and |{a(m) : a(m>k) < 3p}| = 3p - k. - Thomas Ordowski, Jan 22 2009
Let ...,a_i,...,2p,p,3p,...,a_j,... There does not exist a_i > 3p. There does not exist a_j < p. - Thomas Ordowski, Jan 20 2009
Let...,a,...,2p,p,3p,...,b,... All a<3p and b>p. #(a>2p) <= #(b<2p). - Thomas Ordowski, Jan 21 2009
If the definition is changed to require that the GCD of successive terms be a prime power > 1, the sequence stays the same until a(578)=620, at which point a(579)=610 has GCD = 10 with the previous term. - N. J. A. Sloane, Mar 30 2015
For prime p > 2, we have the chain {j : 2|j} -> 2p -> p -> 3p -> {k : 3|k}. The term j introducing 2p must be even, since 2p is an even squarefree semiprime proved by Hofman-Pilipczuk to introduce p itself. Hence no term a(i) such that p | a(i) exists in the sequence for i < n-1, where a(n) = p, leaving 2|j. Similarly, the term k following 3p must be divisible by 3 since the terms mp that are not coprime to p (thus implying p | mp) have m >= 4, thereby large compared to numbers k such that 3|k that belong to the cototient of 3p. For the chain {4, 6, 3, 9, 12}, the term 12 following 3p indeed is 4p, but p = 3; this is the only case of 4p following 3p in the sequence. As a consequence, for i > 1, A073734(A064955(i)-1) = 2 and A073734(A064955(i)+2) = 3.
For Fermat primes p, we have the chain {j : 2|j} -> 2^e-> {2p = 2^e + 2} -> {p = 2^(e-1) + 1} -> 3p -> {k : 3|k}.
a(3) = 4 = 2^2, a(5) = 3 = 2^1 + 1;
a(8) = 8 = 2^3, a(10) = 5 = 2^2 + 1;
a(31) = 32 = 2^5, a(33) = 17 = 2^4 + 1;
a(485) = 512 = 2^9, a(487) = 257 = 2^8 + 1;
a(127354) = 131072 = 2^17, a(127356) = 65537 = 2^16 + 1.
(End)
|
|
REFERENCES
|
N. J. A. Sloane, Seven Staggering Sequences, in Homage to a Pied Puzzler, E. Pegg Jr., A. H. Schoen and T. Rodgers (editors), A. K. Peters, Wellesley, MA, 2009, pp. 93-110.
|
|
LINKS
|
Michael De Vlieger, Annotated plot of a(n) for n=1..120, showing prime p in red, 2p in blue, 3p in green, and other terms in gray.
Michael De Vlieger, Partially annotated log-log scatterplot of a(n) for n=1..1024, showing prime p in red, 2p in blue, 3p in green, and other terms in gray. This plot exhibits three quasi-linear striations, the densest contains both 2p and all "gray" terms outside of the first dozen or so terms in the sequence.
James Keener, Mathematics of EKG [Refers to EKGs found in hospitals, included for comparison.]
J. C. Lagarias, E. M. Rains and N. J. A. Sloane, The EKG sequence, arXiv:math/0204011 [math.NT], 2002.
J. C. Lagarias, E. M. Rains and N. J. A. Sloane, The EKG Sequence, Exper. Math. 11 (2002), 437-446.
|
|
FORMULA
|
a(n) = smallest number not already used such that gcd(a(n), a(n-1)) > 1.
In Lagarias-Rains-Sloane (2002), it is conjectured that almost all a(n) satisfy the asymptotic formula a(n) = n (1+ 1/(3 log n)) + o(n/log n) as n -> oo and that the exceptional terms when the sequence is a prime or 3 times a prime p produce the spikes in the sequence. See the paper for a more precise statement of the conjecture. - N. J. A. Sloane, Mar 07 2015
|
|
EXAMPLE
|
a(2) = 2, a(3) = 4 (gcd(2,4) = 2), a(4) = 6 (gcd(4,6) = 2), a(5) = 3 (gcd(6,3) = 3), a(6) = 9 (6 already used so next number which shares a factor is 9 since gcd(3,9) = 3).
|
|
MAPLE
|
h := array(1..20000); a := array(1..10000); maxa := 300; maxn := 2*maxa; for n from 1 to maxn do h[n] := -1; od: a[1] := 2; h[2] := 1; c := 2; for n from 2 to maxa do for m from 2 to maxn do t1 := gcd(m, c); if t1 > 1 and h[m] = -1 then c := m; a[n] := c; h[c] := n; break; fi; od: od: ap := []: for n from 1 to maxa do ap := [op(ap), a[n]]; od: hp := []: for n from 2 to maxa do hp := [op(hp), h[n]]; od: convert(ap, list); convert(hp, list); # this is very crude!
N:= 1000: # to get terms before the first term > N
V:= Vector(N):
A[1]:= 1:
A[2]:= 2: V[2]:= 1:
for n from 3 do
S:= {seq(seq(k*p, k=1..N/p), p=numtheory:-factorset(A[n-1]))};
for s in sort(convert(S, list)) do
if V[s] = 0 then
A[n]:= s;
break
fi
od;
if V[s] = 1 then break fi;
V[s]:= 1;
od:
|
|
MATHEMATICA
|
maxN = 100; ekg = {1, 2}; unused = Range[3, maxN]; found = True; While[found, found = False; i = 0; While[ !found && i < Length[unused], i++; If[GCD[ekg[[-1]], unused[[i]]] > 1, found = True; AppendTo[ekg, unused[[i]]]; unused = Delete[unused, i]]]]; ekg (* Ayres *)
ekGrapher[s_List] := Block[{m = s[[-1]], k = 3}, While[MemberQ[s, k] || GCD[m, k] == 1, k++ ]; Append[s, k]]; Nest[ekGrapher, {1, 2}, 71] (* Robert G. Wilson v, May 20 2009 *)
|
|
PROG
|
(Haskell)
import Data.List (delete, genericIndex)
a064413 n = genericIndex a064413_list (n - 1)
a064413_list = 1 : f 2 [2..] where
ekg x zs = f zs where
f (y:ys) = if gcd x y > 1 then y : ekg y (delete y zs) else f ys
(PARI)
a1=1; a2=2; v=[1, 2];
for(n=3, 100, a3=if(n<0, 0, t=1; while(vecmin(vector(length(v), i, abs(v[i]-t)))*(gcd(a2, t)-1)==0, t++); t); a2=a3; v=concat(v, a3); );
a(n)=v[n];
(Python)
from fractions import gcd
A064413_list, l, s, b = [1, 2], 2, 3, {}
for _ in range(10**5):
....i = s
....while True:
........if not i in b and gcd(i, l) > 1:
............l, b[i] = i, True
............while s in b:
................b.pop(s)
................s += 1
............break
|
|
CROSSREFS
|
A073734 gives GCD's of successive terms.
See A064664 for the inverse permutation. See A064665-A064668 for the first two infinite cycles of this permutation. A064669 gives cycle representatives.
See A064421 for sequence giving term at which n appears.
|
|
KEYWORD
|
|
|
AUTHOR
|
Jonathan Ayres (Jonathan.ayres(AT)btinternet.com), Sep 30 2001
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|