This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A064413 #181 Mar 22 2025 13:34:17
%S A064413 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,
%T A064413 26,13,39,36,32,34,17,51,42,38,19,57,45,40,44,46,23,69,48,50,52,54,56,
%U A064413 49,63,60,55,65,70,58,29,87,66,62,31,93,72,64,68,74,37,111,75,78,76,80,82
%N 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).
%C A064413 Locally, the graph looks like an EKG (American English) or ECG (British English).
%C A064413 Calculating the square of A064413 and plotting the results shows the EKG behavior even more dramatically - see A104125. - _Parthasarathy Nambi_, Jan 27 2005
%C A064413 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
%C A064413 The permutation has cycles (1) (2) (3, 4, 6, 9, 10, 5) (..., 20, 18, 12, 7, 14, 13, 28, 26, ...) (8) ...
%C A064413 Theorem: (2) The primes appear in increasing order. - J. C. Lagarias, E. M. Rains, _N. J. A. Sloane_, Oct 03 2001
%C A064413 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.
%C A064413 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.
%C A064413 Conjecture: If a(n) != p, then almost everywhere a(n) > n. - _Thomas Ordowski_, Jan 23 2009
%C A064413 Conjecture: lim #(a_n > n) / n = 1, i.e., #(a_n > n) ~ n. - _Thomas Ordowski_, Jan 23 2009
%C A064413 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
%C A064413 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
%C A064413 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
%C A064413 Let...,a,...,2p,p,3p,...,b,... All a<3p and b>p. #(a>2p) <= #(b<2p). - _Thomas Ordowski_, Jan 21 2009
%C A064413 If a(k)=3p then |{a(m):a(m>k)<3p}|=3p-k. - _Thomas Ordowski_, Jan 22 2009
%C A064413 GCD(a(n),n) = A247379(n). - _Reinhard Zumkeller_, Sep 16 2014
%C A064413 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
%C A064413 From _Michael De Vlieger_, Dec 06 2021: (Start)
%C A064413 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.
%C A064413 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}.
%C A064413 a(3) = 4 = 2^2, a(5) = 3 = 2^1 + 1;
%C A064413 a(8) = 8 = 2^3, a(10) = 5 = 2^2 + 1;
%C A064413 a(31) = 32 = 2^5, a(33) = 17 = 2^4 + 1;
%C A064413 a(485) = 512 = 2^9, a(487) = 257 = 2^8 + 1;
%C A064413 a(127354) = 131072 = 2^17, a(127356) = 65537 = 2^16 + 1.
%C A064413 (End)
%D A064413 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.
%H A064413 Zak Seidov, <a href="/A064413/b064413.txt">Table of n, a(n) for n = 1..10000</a>
%H A064413 David L. Applegate, Hans Havermann, Bob Selcoe, Vladimir Shevelev, N. J. A. Sloane, and Reinhard Zumkeller, <a href="http://arxiv.org/abs/1501.01669">The Yellowstone Permutation</a>, arXiv preprint arXiv:1501.01669 [math.NT], 2015 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Sloane/sloane9.html">J. Int. Seq. 18 (2015) 15.6.7</a>.
%H A064413 Michael De Vlieger, <a href="/A064413/a064413.png">Annotated plot of a(n)</a> for n=1..120, showing prime p in red, 2p in blue, 3p in green, and other terms in gray.
%H A064413 Michael De Vlieger, <a href="/A064413/a064413_1.png">Partially annotated log-log scatterplot of a(n)</a> 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.
%H A064413 Michael De Vlieger, <a href="/A064413/a064413.txt">Table of n, a(n)</a> for n = 1..262144.
%H A064413 Michael De Vlieger, <a href="/A064413/a064413_1.txt">Mathematica version of Eric Rains' C Code</a>, 2021.
%H A064413 Diophante.fr, <a href="http://www.diophante.fr/problemes-par-themes/logique/e1-suites-logiques/2254-e121-une-sequence-cordiale"> Les Récreations Mathématiques: E121. Une séquence cordiale</a>.
%H A064413 Gordon Hamilton, <a href="http://www.youtube.com/watch?v=yd2jr30K2R4">The EKG Sequence and the Tree of Numbers</a>
%H A064413 Gordon Hamilton, <a href="http://m.youtube.com/watch?v=Y2KhEW9CSOA">Untitled video related to previous video</a>
%H A064413 Piotr Hofman and Marcin Pilipczuk, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Hofman/hofman1.html">A few new facts about the EKG sequence</a>, J. Integer Seqs., 11 (2008), Article 08.4.2.
%H A064413 James Keener, <a href="http://www.math.utah.edu/~keener/lectures/maw/index.html">Mathematics of EKG</a> [Refers to EKGs found in hospitals, included for comparison.]
%H A064413 J. C. Lagarias, E. M. Rains and N. J. A. Sloane, <a href="http://arXiv.org/abs/math.NT/0204011">The EKG sequence</a>, arXiv:math/0204011 [math.NT], 2002.
%H A064413 J. C. Lagarias, E. M. Rains and N. J. A. Sloane, <a href="http://www.emis.de/journals/EM/expmath/volumes/11/11.3/Lagarias437_446.pdf">The EKG Sequence</a>, Exper. Math. 11 (2002), 437-446.
%H A064413 J. C. Lagarias, E. M. Rains and N. J. A. Sloane, <a href="/A064413/a064413_1.pdf">Plot of a(1) to a(100), with successive points joined by lines.</a>
%H A064413 J. C. Lagarias, E. M. Rains and N. J. A. Sloane, <a href="/A064413/a064413_2.pdf">Terms 800 to 1000, with successive points joined by lines.</a>
%H A064413 J. C. Lagarias, E. M. Rains and N. J. A. Sloane, <a href="/A064413/a064413_3.pdf">The first 1000 terms (represented by dots), successive points not joined.</a>
%H A064413 J. C. Lagarias, E. M. Rains and N. J. A. Sloane, <a href="/A064413/a064413_4.pdf">The first 10000 terms (represented by dots), successive points not joined.</a>
%H A064413 J. C. Lagarias, E. M. Rains and N. J. A. Sloane, <a href="/A064413/a064413_5.pdf">The sequence smoothed by replacing a(n)=p or 3p, p prime > 2, by a(n) = 2p.</a>
%H A064413 Ivars Peterson, <a href="https://www.sciencenews.org/article/ekg-sequence">The EKG Sequence</a>
%H A064413 E. M. Rains, <a href="/A064413/a064413.c.txt">C program</a>
%H A064413 N. J. A. Sloane, <a href="http://neilsloane.com/doc/g4g7.pdf">Seven Staggering Sequences</a>.
%H A064413 N. J. A. Sloane, <a href="/A195264/a195264.pdf">Confessions of a Sequence Addict (AofA2017)</a>, slides of invited talk given at AofA 2017, Jun 19 2017, Princeton. Mentions this sequence.
%H A064413 N. J. A. Sloane, <a href="https://vimeo.com/457349959">Conant's Gasket, Recamán Variations, the Enots Wolley Sequence, and Stained Glass Windows</a>, Experimental Math Seminar, Rutgers University, Sep 10 2020 (video of Zoom talk).
%H A064413 N. J. A. Sloane, <a href="https://vimeo.com/704569041/4ffa06b95e">The On-Line Encyclopedia of Integer Sequences: An illustrated guide with many unsolved problems</a>, Guest Lecture given in Doron Zeilberger's Experimental Mathematics Math640 Class, Rutgers University, Spring Semester, Apr 28 2022: <a href="https://sites.math.rutgers.edu/~zeilberg/EM22/C27.pdf">Slides</a>; <a href="http://NeilSloane.com/doc/Math640.04.2022.pdf">Slides (an alternative source)</a>.
%H A064413 N. J. A. Sloane, <a href="https://arxiv.org/abs/2301.03149">"A Handbook of Integer Sequences" Fifty Years Later</a>, arXiv:2301.03149 [math.NT], 2023, p. 16.
%H A064413 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/EKGSequence.html">EKG Sequence</a>
%H A064413 <a href="/index/Ed#EKG">Index entries for sequences related to EKG sequence</a>
%H A064413 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A064413 a(n) = smallest number not already used such that gcd(a(n), a(n-1)) > 1.
%F A064413 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
%e A064413 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).
%p A064413 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!
%p A064413 N:= 1000: # to get terms before the first term > N
%p A064413 V:= Vector(N):
%p A064413 A[1]:= 1:
%p A064413 A[2]:= 2: V[2]:= 1:
%p A064413 for n from 3 do
%p A064413 S:= {seq(seq(k*p,k=1..N/p),p=numtheory:-factorset(A[n-1]))};
%p A064413 for s in sort(convert(S,list)) do
%p A064413 if V[s] = 0 then
%p A064413 A[n]:= s;
%p A064413 break
%p A064413 fi
%p A064413 od;
%p A064413 if V[s] = 1 then break fi;
%p A064413 V[s]:= 1;
%p A064413 od:
%p A064413 seq(A[i],i=1..n-1); # _Robert Israel_, Jan 18 2016
%t A064413 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 *)
%t A064413 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 *)
%o A064413 (Haskell)
%o A064413 import Data.List (delete, genericIndex)
%o A064413 a064413 n = genericIndex a064413_list (n - 1)
%o A064413 a064413_list = 1 : f 2 [2..] where
%o A064413 ekg x zs = f zs where
%o A064413 f (y:ys) = if gcd x y > 1 then y : ekg y (delete y zs) else f ys
%o A064413 -- _Reinhard Zumkeller_, May 01 2014, Sep 17 2011
%o A064413 (PARI)
%o A064413 a1=1; a2=2; v=[1,2];
%o A064413 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););
%o A064413 a(n)=v[n];
%o A064413 /* _Benoit Cloitre_, Sep 23 2012 */
%o A064413 (Python)
%o A064413 from math import gcd
%o A064413 A064413_list, l, s, b = [1,2], 2, 3, {}
%o A064413 for _ in range(10**5):
%o A064413 i = s
%o A064413 while True:
%o A064413 if not i in b and gcd(i, l) > 1:
%o A064413 A064413_list.append(i)
%o A064413 l, b[i] = i, True
%o A064413 while s in b:
%o A064413 b.pop(s)
%o A064413 s += 1
%o A064413 break
%o A064413 i += 1 # _Chai Wah Wu_, Dec 08 2014
%Y A064413 A073734 gives GCD's of successive terms.
%Y A064413 See A064664 for the inverse permutation. See A064665-A064668 for the first two infinite cycles of this permutation. A064669 gives cycle representatives.
%Y A064413 See A064421 for sequence giving term at which n appears.
%Y A064413 See A064424, A074177 for records.
%Y A064413 Cf. A064955 & A352194 (prime positions), A195376 (parity), A064957 (positions of odd terms), A064953 (positions of even terms), A064426 (first differences).
%Y A064413 See A169857 and A119415 for the effect of changing the start.
%Y A064413 Cf. A240024 (nonprime version).
%Y A064413 Cf. A152458 (fixed points), A247379, A247383.
%Y A064413 For other initial terms, see A169841, A169837, A169843, A169855, A169849.
%Y A064413 A256417 is a smoothed version.
%Y A064413 See also A255582, A256466, A257218, A257311-A257315, A257405, A253279 (two-dimensional analog).
%Y A064413 See also A276127.
%K A064413 nonn,nice,easy,look,hear
%O A064413 1,2
%A A064413 Jonathan Ayres (Jonathan.ayres(AT)btinternet.com), Sep 30 2001
%E A064413 More terms from _Naohiro Nomoto_, Sep 30 2001
%E A064413 Entry extensively revised by _N. J. A. Sloane_, Oct 10 2001