1,2

Locally, the graph looks like an EKG (American English) or ECG (British English).

Calculating the square ofA064413and plotting the results shows the EKG behavior even more dramatically - seeA104125.-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 (seeA256417). 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 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

FromMichael De Vlieger,Dec 06 2021: (Start)

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 andA073734(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)

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.

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 andJ. Int. Seq. 18 (2015) 15.6.7.

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.

Michael De Vlieger,Table of n, a(n)for n = 1..262144.

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.

N. J. A. Sloane,Conant's Gasket, Recamán Variations, the Enots Wolley Sequence, and Stained Glass Windows,Experimental Math Seminar, Rutgers University, Sep 10 2020 (video of Zoom talk).

N. J. A. Sloane,The On-Line Encyclopedia of Integer Sequences: An illustrated guide with many unsolved problems,Guest Lecture given in Doron Zeilberger's Experimental Mathematics Math640 Class, Rutgers University, Spring Semester, Apr 28 2022:Slides;Slides (an alternative source).

N. J. A. Sloane,"A Handbook of Integer Sequences" Fifty Years Later,arXiv:2301.03149 [math.NT], 2023, p. 16.

Eric Weisstein's World of Mathematics,EKG Sequence

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

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

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

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 *)

(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

A073734gives GCD's of successive terms.

SeeA064664for the inverse permutation. SeeA064665-A064668for the first two infinite cycles of this permutation.A064669gives cycle representatives.

SeeA064421for sequence giving term at which n appears.

SeeA064424,A074177for records.

Cf.A064955&A352194(prime positions),A195376(parity),A064957(positions of odd terms),A064953(positions of even terms),A064426(first differences).

SeeA169857andA119415for the effect of changing the start.

Cf.A240024(nonprime version).

Cf.A152458(fixed points),A247379,A247383.

For other initial terms, seeA169841,A169837,A169843,A169855,A169849.

A256417is a smoothed version.

See alsoA255582,A256466,A257218,A257311-A257315,A257405,A253279(two-dimensional analog).

See alsoA276127.

Sequence in context:A362015A374284A096665*A352187A357963A357994

Adjacent sequences:A064410A064411A064412*A064414A064415A064416

nonn,nice,easy,look,hear

Jonathan Ayres (Jonathan.ayres(AT)btinternet.com), Sep 30 2001

More terms fromNaohiro Nomoto,Sep 30 2001

Entry extensively revised byN. J. A. Sloane,Oct 10 2001

approved