This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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). 197
 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). Calculating the square of A064413 and plotting the results shows the EKG behavior even more dramatically - see A104125. - Parthasarathy Nambi, Jan 27 2005 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(mk) > 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 a(k)=3p then |{a(m):a(m>k)<3p}|=3p-k. - Thomas Ordowski, Jan 22 2009 GCD(a(n),n) = A247379(n). - Reinhard Zumkeller, Sep 16 2014 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 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 Zak Seidov, Table of n, a(n) for n = 1..10000 David L. Applegate, Hans Havermann, Bob Selcoe, Vladimir Shevelev, N. J. A. Sloane, and Reinhard Zumkeller, The Yellowstone Permutation, arXiv preprint arXiv:1501.01669 [math.NT], 2015 and J. Int. Seq. 18 (2015) 15.6.7.. Diophante.fr, Les Récreations Mathématiques: E121. Une séquence cordiale. Gordon Hamilton, The EKG Sequence and the Tree of Numbers Gordon Hamilton, Untitled video related to previous video Piotr Hofman and Marcin Pilipczuk, A few new facts about the EKG sequence, J. Integer Seqs., 11 (2008), Article 08.4.2. 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. J. C. Lagarias, E. M. Rains and N. J. A. Sloane, Plot of a(1) to a(100), with successive points joined by lines. J. C. Lagarias, E. M. Rains and N. J. A. Sloane, Terms 800 to 1000, with successive points joined by lines. J. C. Lagarias, E. M. Rains and N. J. A. Sloane, The first 1000 terms (represented by dots), successive points not joined. J. C. Lagarias, E. M. Rains and N. J. A. Sloane, The first 10000 terms (represented by dots), successive points not joined. J. C. Lagarias, E. M. Rains and N. J. A. Sloane, The sequence smoothed by replacing a(n)=p or 3p, p prime > 2, by a(n) = 2p. Ivars Peterson, The EKG Sequence E. M. Rains, C program N. J. A. Sloane, Seven Staggering Sequences. N. J. A. Sloane, Confessions of a Sequence Addict (AofA2017), slides of invited talk given at AofA 2017, Jun 19 2017, Princeton. Mentions this sequence. Eric Weisstein's World of Mathematics, EKG Sequence 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: seq(A[i], i=1..n-1); # Robert Israel, Jan 18 2016 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 -- Reinhard Zumkeller, May 01 2014, Sep 17 2011 (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]; /* Benoit Cloitre, Sep 23 2012 */ (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: ............A064413_list.append(i) ............l, b[i] = i, True ............while s in b: ................b.pop(s) ................s += 1 ............break ........i += 1 # Chai Wah Wu, Dec 08 2014 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. See A064424, A074177 for records. Cf. A064955 (prime positions), A195376 (parity), A064957 (positions of odd terms), A064953 (positions of even terms), A064426 (first differences). See A169857 and A119415 for the effect of changing the start. Cf. A240024 (nonprime version). Cf. A152458 (fixed points), A247379, A247383. For other initial terms, see A169841, A169837, A169843, A169855, A169849. A256417 is a smoothed version. See also A255582, A256466, A257218, A257311-A257315, A257405, A253279 (two-dimensional analog). See also A276127. Sequence in context: A181548 A207779 A096665 * A255348 A122280 A291577 Adjacent sequences:  A064410 A064411 A064412 * A064414 A064415 A064416 KEYWORD nonn,nice,easy,look,hear AUTHOR Jonathan Ayres (Jonathan.ayres(AT)btinternet.com), Sep 30 2001 EXTENSIONS More terms from Naohiro Nomoto, Sep 30 2001 Entry extensively revised by N. J. A. Sloane, Oct 10 2001 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 18 12:12 EST 2018. Contains 317306 sequences. (Running on oeis4.)