|
%I #237 Mar 13 2019 19:31:24
%S 1,2,3,4,6,8,9,10,12,5,14,15,7,18,21,16,27,20,33,24,11,26,22,13,28,39,
%T 32,30,44,25,34,35,17,40,51,36,68,42,52,45,38,48,19,46,57,23,54,69,50,
%U 63,55,49,60,56,65,58,70,29,62,87,31,66,93,64,75,72,85,74,80,37,76,111
%N a(n) = n if n <= 3, otherwise the smallest number not occurring earlier such that gcd(a(n),a(n-2)) > gcd(a(n),a(n-1)).
%C Conjecture: The sequence is infinite (that is, a(n) always exists).
%C _Ray Chandler_ reports that the sequence certainly exists for 10^7 terms, Apr 02 2015. _John P. Linderman_ confirms this, and has extended the sequence to 12.9 million terms, Apr 09 2015. Extended to 50 million terms by _John Mason_ Apr 21 2015. _John P. Linderman_ reached 150 million terms on May 04 2015, 2.5 billion terms on Jun 29 2015, and 5 billion terms on Apr 07 2017 (see attached letter).
%C Note that if a(n) ever divides a(n+1), the sequence will terminate. This has not happened in the first 2.5 billion terms (see the Linderman links), but there have been some close calls. For example, at n=9671, a(9671) = 4973 = a prime p, and a(9672) = 9947 = 2p+1. Conversely, if a(n) never divides a(n+1), the sequence is infinite. - _N. J. A. Sloane_, Mar 22 2015 and Jun 06 2015
%C Conjecture: The sequence is a permutation of the natural numbers.
%C Conjectures: 1) For k>=3, except for k=5, if a(n) = prime(k), then a(n-2) = 2*prime(k) and a(n+2) = 3*prime(k). This conjecture was verified by _Peter J. C. Moses_ for n <= 5000. - _Vladimir Shevelev_, Feb 09 2015. This conjecture verified for n <= 10^7. - _Ray Chandler_, Apr 02 2015. Extended to n <= 10^9. - _John Mason_, Jun 08 2016
%C 2) For k>=3, except for k=4, if a(n)=prime(k)^2, then a(n-2) = prime(k)^2 + prime(k). This conjecture was verified by _Peter J. C. Moses_ for n <= 35000. - _Vladimir Shevelev_, Feb 12 2015. This conjecture verified for n <= 394349. - _Ray Chandler_, Mar 07 2015. This conjecture is false - for n = 4488245, a(n) = 2137^2, but a(n-2) = 2137^2 + 2*2137. - _Ray Chandler_, Mar 30 2015. Next are n = 30655601, a(n) = 5581^2, but a(n-2) = 5581^2 + 2*5581, and n = 922447261, a(n) = 30577^2, but a(n-2) = 30577^2 + 2*30577. - _John Mason_, Sep 15 2016
%C Theorem: a(n) does not divide a(n-1). For suppose a(n-2)=x, a(n-1)=b*c, a(n)=c. Then gcd(x,c) <= c, and gcd(b*c,c) = c, which contradicts the definition of a(n). - _N. J. A. Sloane_, Mar 22 2015
%C Theorem: If a(n-2) is prime AND a(n) EXISTS then a(n) is a multiple of a(n-2). For: by sequence definition, assuming a(n-2) = p, prime, then gcd(a(n),p) > gcd(a(n),a(n-1)); hence gcd(a(n),p) > 1; but p is prime and has only 1 and itself as divisors; so gcd(a(n),p)=p, and so a(n) is a multiple of p. (Weaker than the similar conjecture above.) - _John Mason_, Apr 15 2015 [WORDS IN CAPS ADDED BY _N. J. A. Sloane_, Apr 16 2015]
%C Theorem: If a(n) EXISTS AND a(n) > a(n-2)/2 then a(n) is composite. For: suppose instead that a(n)=p, prime; then by sequence definition, gcd(p,a(n-2)) > gcd(p,a(n-1)); hence gcd(p,a(n-2))>1; hence a(n-2) is a multiple of p; but a(n-2) < 2p so we have a contradiction; hence a(n) is composite. This theorem improves the efficiency of some sequence generation algorithms. - _John Mason_, Apr 15 2015 [WORDS IN CAPS ADDED BY _N. J. A. Sloane_, Apr 16 2015] [Further corrected by _John Mason_, May 28 2017]
%C Theorem: If a(n-2)=mp for some prime p, and m divides a(n-1), then a(n), if it exists, is a multiple of p (generalization of previous theorem, which is the special case of m=1). See for example a(33)=17, a(35)=51, a(37)=68; a(37) is a multiple of 17 because a(36) is a multiple of 3, which is "m" in a(35). (It follows that if a(n-2) / gcd(a(n-2), a(n-1)) is p, prime, then a(n), if it exists, is a multiple of p. - _John Mason_, May 19 2015)
%C Proof: consider consecutive terms mp,y,z for prime p, and m dividing y. By sequence definition gcd(z,mp)>gcd(z,y). Suppose that z is not a multiple of p. Then gcd(z,mp)=gcd(z,m), and so gcd(z,m)>gcd(z,y). Since m divides y, then gcd(z,m)>gcd(z,mq) for q = y/m, but this is clearly impossible. Hence z is a multiple of p. - _John Mason_, Apr 17 2015
%C Theorem: The first occurrences of the primes as factors of terms of the sequence are in ascending order, and without gaps (that is, 2 precedes 3, 3 precedes 5 (factor of 10), 5 precedes 7 (factor of 14), ...).
%C Proof: Suppose a(n)=mp is the first term having p as a factor. Then the theory states that q, prime and <p, must be a factor of some preceding term. Suppose, on the contrary, that some q, prime and <p, is not a factor of any preceding term (a(1) through a(n-1)). Then, by sequence definition, gcd(mp,a(n-2))>gcd(mp,a(n-1)). As a(n) is the first to have p as a factor, p does not divide a(n-2) and a(n-1), and neither does q. Hence gcd(mp,a(n-2))=gcd(m,a(n-2)) and gcd(mp,a(n-1))= gcd(m,a(n-1)). Hence gcd(m,a(n-2)) > gcd(m,a(n-1)). Hence gcd(mq,a(n-2)) > gcd(mq,a(n-1)). Hence mq, < mp, would have satisfied the conditions of the sequence for a(n), which is a contradiction. Hence no such prime q exists. - _John Mason_, Apr 17 2015
%C Theorem: The first occurrence of a prime p as a factor of a term in the sequence is in a term that is not equal to p itself.
%C Proof: Suppose a(n)=p, prime, the first term having p as a factor. Then gcd(p,a(n-2))=1, and therefore cannot be greater than gcd(p,a(n-1)), a contradiction of the rules of sequence construction. - _John Mason_, Apr 17 2015
%C Conjecture. The primes exist as elementary terms of the sequence in ascending order. - _John Mason_, Apr 17 2015
%C _John Mason_ reports that each prime p seems to appear at a term n which is approaching 2p, as p increases. See A256213. - _N. J. A. Sloane_, Apr 16 2015
%C Conjecture. For any n > 4, the lowest value x missing from a(1) thru a(n) is prime. - _John Mason_, Apr 29 2015. In fact, taking into account that, apparently, prime p appears in the sequence at position circa 2p, we may conjecture that the lowest k values missing from a(1) thru a(n) are prime, where k = pi(n)-pi(n/2) - see A000720. - _John Mason_, Jun 03 2015
%C Theorem: if a(n) = p for some prime p > 3, then a(n-2) is a multiple of p. As a direct consequence, if all prime factors of a(n-2) are already present in the sequence, then a(n), if it exists, is composite.
%C Proof: by sequence definition, unless p=2 or 3, gcd(p,a(n-2)) > gcd(p,a(n-1)), and hence gcd(p,a(n-2))>1, and hence a(n-2) is a multiple of p. - _John Mason_, May 19 2015
%C First differs from A255582 at a(29). - _Omar E. Pol_, May 21 2015
%C Conjecture. For n > 778, if a(n) < n, then a(n) is prime. This has been confirmed for n through 10^9. - _John Mason_, Jun 03 2015 [Corrected, following suggestion by _John P. Linderman_, by _John Mason_, May 28 2017]
%C Conjecture. As for "Conjecture 1" above, which is its mirror image, except for n=2,3,21, corresponding to primes 2,3,11, if a(n-2)=mp is the first occurrence of prime p as a factor in the sequence, then m=2 and a(n)=p. Also, if a(n-2)=mp is the first occurrence of prime p as a factor in the sequence, then p does not divide a(n-1). - _John Mason_, May 31 2016
%C Theorem 1: If a(n) is the first term having p (prime) as a factor, then a(n+1), if it exists, is not a multiple of p. For proof, see links. - _John Mason_, Jul 26 2016
%C Theorem 2: If a(n)=cp is the first occurrence of prime p as a factor (n >3), than c has exactly one distinct prime factor. In other words, c may be expressed as k^i for some prime k, and i > 0.
%C Corollary. If a(n)=cp is the first occurrence of prime p as a factor (n >3), and as a consequence c= k^i for some prime k, and i > 0, then k^i divides a(n-2) and k^(i-1) is the maximum power of k that divides a(n-1).
%C Theorem 3 . If a(n) = 2p is the first term having p (prime) as a factor, then a(n-1) is odd and a(n-2) is even.
%C Theorem 4. If a(n) = 2p is the first term having p (prime) as a factor, then a(n+2), if it exists, is either p or 2u for some integer u such that 2u < p. (Note that it is conjectured to be always p, and observation confirms the conjecture.)
%C Theorem 5, generalization of Theorem 4. If a(n) = cp is the first term having p (prime) as a factor (n >3), and as a consequence c=k^i for prime k and i>0, then a(n+2), if it exists, is either p or ku for some integer u such that ku < p. (Note that it is conjectured to be always p, and observation confirms the conjecture.)
%C Theorem 6. If a(n) = cp is first term having p, prime, as a factor (n >3), and a(n+2)=p, then a(n+3) exists, and is not a multiple of p, and so does not terminate the sequence.
%C Theorem 7. If a(n) = cp is first term having p, prime, as a factor (n >3), and a(n+2)=p, then a(n+4) exists and is 2p or 3p. Also, a(n+5) exists.
%C For proofs, see links. - _John Mason_, Aug 03 2016
%C Theorem 8: If the sequence is infinite, it is a permutation of the positive integers. For proof, see link. - _John Mason_, Sep 14 2016
%C Conjecture: After 2 and 3, no two primes are consecutive terms. This conjecture is derivable from the previous conjecture : "For k>=3, except for k=5, if a(n) = prime(k), then a(n-2) = 2*prime(k) ...". For, if sequence has terms z,2p,2q,p,q for primes p & q, then gcd(2q,z)>gcd(2q,2p)=2. Hence q divides z. So terms are mq,2p,2q,p,q. So we could have used q in place of 2q. - _John Mason_, May 28 2017
%H Peter J. C. Moses and Ray Chandler, <a href="/A254077/b254077.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from Peter J. C. Moses)
%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.
%H John P. Linderman, <a href="/A254077/a254077.txt">Table of n, a(n) for n = 1..1000000 (about 13MB)</a>
%H John P. Linderman, <a href="/A254077/a254077-7a.txt.gz">Table of n, a(n) for n = 1..12940331 (about 61MB)</a>
%H John P. Linderman, <a href="/A254077/a254077_1.txt">Go program</a> [Revised Jun 29 2015]
%H John P. Linderman, <a href="/A254077/a254077_5.pdf">Notes on computation of first 5 billion terms</a>
%H John Mason, <a href="/A254077/a254077.pdf">Some observations</a>
%H John Mason, <a href="/A254077/a254077_2.pdf">Some proofs</a>
%H John Mason, <a href="/A254077/a254077_4.pdf">Proof of theorem: If the sequence is infinite, it is a permutation of the positive integers</a>
%t f[n_] := Block[{s = Range@ n, j, k}, For[k = 4, k <= n, k++, j = 4; While[Nand[GCD[j, s[[k - 2]]] > GCD[j, s[[k - 1]]], !MemberQ[Take[s, k - 1], j]], j++]; s[[k]] = j]; s]; f@ 72 (* _Michael De Vlieger_, Apr 15 2015 *)
%o (Haskell)
%o a254077 n = a254077_list !! (n-1)
%o a254077_list = 1 : 2 : 3 : f 2 3 [4..] where
%o f u v ws = g ws where
%o g (x:xs) = if gcd x u > gcd x v then x : f v x (delete x ws) else g xs
%o -- _Reinhard Zumkeller_, May 05 2015
%Y Cf. A098550, A247225, A247942, A249167, A251604, A256974, A318826.
%Y For indices of primes see A256213. Sequence mod 2 is A257585.
%Y Changing > in definition to >= produces A255582 (which DOES exist).
%Y Cf. A256528 (partial sums).
%K nonn
%O 1,2
%A _Vladimir Shevelev_, Jan 25 2015
%E More terms from _Peter J. C. Moses_, Jan 25 2015
|
