cp's OEIS Frontend

A175938 Repeat: Take next nonprime, next prime, next nonprime, then reverse the order.

%I A175938 #28 Apr 04 2015 21:45:22
%S A175938 4,2,1,8,3,6,10,5,9,14,7,12,16,11,15,20,13,18,22,17,21,25,19,24,27,23,
%T A175938 26,30,29,28,33,31,32,35,37,34,38,41,36,40,43,39,44,47,42,46,45,53,49,
%U A175938 48,59,51,50,61,54,52,67,56,55,71
%N A175938 Repeat: Take next nonprime, next prime, next nonprime, then reverse the order.
%C A175938 Start with first nonprime 1 and first prime 2. To obtain the first three terms take first nonprime 1, first prime 2, next nonprime 4, then reverse the order to get 4, 2, 1. Next step: take next nonprime 6, next prime 3, next nonprime 8 and reverse to get 8, 3, 6. It is obvious that the sequence is a permutation of positive integers. It is closely related to the lexicographically earliest permutation of the natural numbers such that each prime number is followed by exactly two composite numbers (cf. A115316). It is also related in a certain way to the number of primes <= n, PrimePi(n) (cf. A000720).
%C A175938 Conjecture: The permutation has exactly 12 fixed points: 2, 6, 9, 12, 15, 18, 21, 24, 29, 40, 46, 49.
%C A175938 From _D. S. McNeil_, Dec 09 2010: (Start)
%C A175938 The conjecture is true, roughly because the primes are packed far too closely (one every three terms, after all) and as a result the nonprimes are too spread out.
%C A175938 First consider the primes: after permutation the k-th prime p shows up at 3*k-1, so to be a fixed point we need p=3*k-1.  Note that k=prime_pi(p), so we seek solutions to p=3*pi(p)-1, which cannot occur if p > 3*pi(p)-1 (i.e., if the prime is larger than its destination), or equivalently if pi(p) < (p+1)/3.  Using pi(n) < 1.25506*n/log(n) for n > 1, we find there can be no prime fixed points for p >= 40.  Inspection reveals only 2 and 29.
%C A175938 Now consider the nonprimes: after permutation the k-th nonprime r appears either at 3*(k+1)/2 (if k is odd) or 3*k/2-2 (if k is even). Write k = nonprime_pi(r) = r-pi(r).  To prove r appears at an index > r, it suffices to show 3*k/2-2 > r, or pi(r) < r/3 - 4/3.  Again, we have that pi(n) < 1.25506*n/log(n), which rules out nonprime fixed points with r >= 58.  By inspection we find the remaining terms, and the set is complete.  QED.  I would appreciate it if someone would check this proof. (End)
%C A175938 The first trisection of the sequence equals the second bisection of the nonprimes: a(3*k-2) = A018252(2*k), k > 0.
%C A175938 The second trisection of the sequence equals the primes: a(3*k-1) = A000040(k), k > 0.
%C A175938 The third trisection of the sequence equals the first bisection of the nonprimes: a(3*k) = A018252(2*k-1), k > 0.
%C A175938 In other words: Sequence is the interleaving of second bisection of A018252, A000040, first bisection of A018252.
%C A175938 Sequence is the concatenation of consecutive sections of length 3 reversed of A115316.
%t A175938 pr=Prime[Range[1000]];np=Complement[Range[pr[[-1]]],pr];
%t A175938 FL=Flatten@Transpose[{Table[np[[k]],{k,2,1000,2}],Take[pr,500],Table[np[[k]],{k,1,999,2}]}]
%Y A175938 Cf. A000040, A018252, A002808, A115316, A000720.
%K A175938 nonn
%O A175938 1,1
%A A175938 _Zak Seidov_, Dec 06 2010