login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

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

%I #171 Sep 28 2023 02:06:47

%S 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 26,13,39,36,32,34,17,51,42,38,19,57,45,40,44,46,23,69,48,50,52,54,56,

%U 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 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 Locally, the graph looks like an EKG (American English) or ECG (British English).

%C Calculating the square of A064413 and plotting the results shows the EKG behavior even more dramatically - see A104125. - _Parthasarathy Nambi_, Jan 27 2005

%C 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 The permutation has cycles (1) (2) (3, 4, 6, 9, 10, 5) (..., 20, 18, 12, 7, 14, 13, 28, 26, ...) (8) ...

%C Theorem: (2) The primes appear in increasing order. - J. C. Lagarias, E. M. Rains, _N. J. A. Sloane_, Oct 03 2001

%C 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 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 Conjecture: If a(n) != p, then almost everywhere a(n) > n. - _Thomas Ordowski_, Jan 23 2009

%C Conjecture: lim #(a_n > n) / n = 1, i.e., #(a_n > n) ~ n. - _Thomas Ordowski_, Jan 23 2009

%C 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 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 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 Let...,a,...,2p,p,3p,...,b,... All a<3p and b>p. #(a>2p) <= #(b<2p). - _Thomas Ordowski_, Jan 21 2009

%C If a(k)=3p then |{a(m):a(m>k)<3p}|=3p-k. - _Thomas Ordowski_, Jan 22 2009

%C GCD(a(n),n) = A247379(n). - _Reinhard Zumkeller_, Sep 16 2014

%C 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 From _Michael De Vlieger_, Dec 06 2021: (Start)

%C 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 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 a(3) = 4 = 2^2, a(5) = 3 = 2^1 + 1;

%C a(8) = 8 = 2^3, a(10) = 5 = 2^2 + 1;

%C a(31) = 32 = 2^5, a(33) = 17 = 2^4 + 1;

%C a(485) = 512 = 2^9, a(487) = 257 = 2^8 + 1;

%C a(127354) = 131072 = 2^17, a(127356) = 65537 = 2^16 + 1.

%C (End)

%D 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 Zak Seidov, <a href="/A064413/b064413.txt">Table of n, a(n) for n = 1..10000</a>

%H 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 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 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 Michael De Vlieger, <a href="/A064413/a064413.txt">Table of n, a(n)</a> for n = 1..262144.

%H 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 Gordon Hamilton, <a href="http://www.youtube.com/watch?v=yd2jr30K2R4">The EKG Sequence and the Tree of Numbers</a>

%H Gordon Hamilton, <a href="http://m.youtube.com/watch?v=Y2KhEW9CSOA">Untitled video related to previous video</a>

%H 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 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 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 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 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 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 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 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 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 Ivars Peterson, <a href="https://www.sciencenews.org/article/ekg-sequence">The EKG Sequence</a>

%H E. M. Rains, <a href="/A064413/a064413.c.txt">C program</a>

%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/g4g7.pdf">Seven Staggering Sequences</a>.

%H 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 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EKGSequence.html">EKG Sequence</a>

%H <a href="/index/Ed#EKG">Index entries for sequences related to EKG sequence</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F a(n) = smallest number not already used such that gcd(a(n), a(n-1)) > 1.

%F 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 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 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 N:= 1000: # to get terms before the first term > N

%p V:= Vector(N):

%p A[1]:= 1:

%p A[2]:= 2: V[2]:= 1:

%p for n from 3 do

%p S:= {seq(seq(k*p,k=1..N/p),p=numtheory:-factorset(A[n-1]))};

%p for s in sort(convert(S,list)) do

%p if V[s] = 0 then

%p A[n]:= s;

%p break

%p fi

%p od;

%p if V[s] = 1 then break fi;

%p V[s]:= 1;

%p od:

%p seq(A[i],i=1..n-1); # _Robert Israel_, Jan 18 2016

%t 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 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 (Haskell)

%o import Data.List (delete, genericIndex)

%o a064413 n = genericIndex a064413_list (n - 1)

%o a064413_list = 1 : f 2 [2..] where

%o ekg x zs = f zs where

%o f (y:ys) = if gcd x y > 1 then y : ekg y (delete y zs) else f ys

%o -- _Reinhard Zumkeller_, May 01 2014, Sep 17 2011

%o (PARI)

%o a1=1; a2=2; v=[1,2];

%o 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 a(n)=v[n];

%o /* _Benoit Cloitre_, Sep 23 2012 */

%o (Python)

%o from fractions import gcd

%o A064413_list, l, s, b = [1,2], 2, 3, {}

%o for _ in range(10**5):

%o ....i = s

%o ....while True:

%o ........if not i in b and gcd(i,l) > 1:

%o ............A064413_list.append(i)

%o ............l, b[i] = i, True

%o ............while s in b:

%o ................b.pop(s)

%o ................s += 1

%o ............break

%o ........i += 1 # _Chai Wah Wu_, Dec 08 2014

%Y A073734 gives GCD's of successive terms.

%Y See A064664 for the inverse permutation. See A064665-A064668 for the first two infinite cycles of this permutation. A064669 gives cycle representatives.

%Y See A064421 for sequence giving term at which n appears.

%Y See A064424, A074177 for records.

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

%Y See A169857 and A119415 for the effect of changing the start.

%Y Cf. A240024 (nonprime version).

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

%Y For other initial terms, see A169841, A169837, A169843, A169855, A169849.

%Y A256417 is a smoothed version.

%Y See also A255582, A256466, A257218, A257311-A257315, A257405, A253279 (two-dimensional analog).

%Y See also A276127.

%K nonn,nice,easy,look,hear

%O 1,2

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

%E More terms from _Naohiro Nomoto_, Sep 30 2001

%E Entry extensively revised by _N. J. A. Sloane_, Oct 10 2001

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 10:55 EDT 2024. Contains 371241 sequences. (Running on oeis4.)