

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(n1).


322



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 LagariasRainsSloane, proved by HofmanPilipczuk.
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 LagariasRainsSloane, proved by HofmanPilipczuk.
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 : 2j} > 2p > p > 3p > {k : 3k}. The term j introducing 2p must be even, since 2p is an even squarefree semiprime proved by HofmanPilipczuk to introduce p itself. Hence no term a(i) such that p  a(i) exists in the sequence for i < n1, where a(n) = p, leaving 2j. 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 3k 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 : 2j} > 2^e> {2p = 2^e + 2} > {p = 2^(e1) + 1} > 3p > {k : 3k}.
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. 93110.


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 loglog 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 quasilinear 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), 437446.


FORMULA

a(n) = smallest number not already used such that gcd(a(n), a(n1)) > 1.
In LagariasRainsSloane (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[n1]))};
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 A064665A064668 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



