A073846 - OEIS

%I #101 Mar 10 2021 01:22:41

%S 1,2,4,3,6,5,8,7,9,11,10,13,12,17,14,19,15,23,16,29,18,31,20,37,21,41,

%T 22,43,24,47,25,53,26,59,27,61,28,67,30,71,32,73,33,79,34,83,35,89,36,

%U 97,38,101,39,103,40,107,42,109,44,113,45,127,46,131,48,137,49,139,50

%N a(1) = 1; thereafter, every even-indexed term is prime and every odd-indexed term is composite.

%C Equals A067747 shifted by one position. a(n) = A067747(n-1) [for n>1]. - _R. J. Mathar_, Apr 01 2007

%C From _Chayim Lowen_, Aug 12 2015: (Start)

%C Consider f(n,k) = a(f(n,k-1)) with f(n,0) = n. Let us also define f(n,k) for negative values of k as well using: f(n,k-1) = A073898(f(n,k)) where A073898(a(n)) = a(A073898(n)) = n. Let us denote the sequence {f(n,i)} for integers i by R#(n). It is clear that if a is a value in R#(b), R#(a) is just R#(b) with a different offset. Therefore, unless there is a need to do otherwise, let us denote each sequence by its lowest value. These sequences can only behave in one of two ways. They can either be periodic with f(n,m) = f(n,0) for some m, or they can include infinitely many distinct values. Here is the behavior of R#(n) for n<=100:

%C    * R#(1), R#(2) and R#(9) are 1-cycles.

%C    * R#(3), R#(5), R#(7), R#(10) and R#(12) are 2-cycles.

%C    * R#(14), R#(62) and R#(84) are 3-cycles.

%C    * R#(92) is a 6-cycle.

%C    * R#(18) is a 22-cycle.

%C    * R#(34) (A261314) has been checked up to f(34,86) = 1091595086717, R#(42) up to f(42,108) = 106838266736, R#(50) up to f(50,98) = 1078406742163, R#(60) up to f(60,80) = 765456394363, R#(74) up to f(74,78) = 687059343029, R#(82) up to f(82,75) = 682580868743  R#(86) up to f(86,74) = 182831963148, R#(88) up to f(88,66) = 719074799059, and R#(98) up to f(98,88) = 641383978721 without repeated values. Hence, their periods are either extremely large or nonexistent (infinite). I conjecture that the latter is the case. Note that these sequences are not necessarily all distinct as any two may simply be the same sequence with a large offset.

%C For all other n<=100, a(n) is included in one of the above sequences. (End)

%C Conjecturally, the integers that belong to one of these cycles are: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 35, 37, 39, 41, 43, 47, 53, 62, 84, 87, 92, 121, 127, 132, 135, 181, 199, 205, 317. - _Michel Marcus_, Mar 07 2021

%H Reinhard Zumkeller, <a href="/A073846/b073846.txt">Table of n, a(n) for n = 1..10000</a>

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

%F a(2*n-1) = A018252(n); a(2*n) = A000040(n). - _Reinhard Zumkeller_, Jan 29 2014

%F a(n) = A018252(ceiling(n/2))*A000035(n) + A000040(ceiling(n/2))*A059841(n), equivalent to _Reinhard Zumkeller_'s formula. - _Chayim Lowen_, Jul 29 2015

%F a(2n)/a(2n-1) ~ log(n). - _Thomas Ordowski_, Sep 10 2015

%p N:= 100: # to get a(1) to a(2*N).

%p p:= ithprime(N):

%p P,NP:= selectremove(isprime,[$1..p]):

%p seq(op([NP[i],P[i]]),i=1..N); # _Robert Israel_, Dec 22 2014

%t Composite[n_Integer] := FixedPoint[n + PrimePi[ # ] + 1 &, n]; Join[{1}, Flatten[ Transpose[{Table[Prime[n], {n, 1, 35}], Table[Composite[n], {n, 1, 35}]}]]]

%t f[upto_]:=Module[{prs=Prime[Range[PrimePi[upto]]],comps},comps= Complement[ Range[upto],prs];Riffle[Take[comps,Length[prs]],prs]]; f[150] (* _Harvey P. Dale_, Dec 03 2011 *)

%o (Haskell)

%o import Data.List (transpose)

%o a073846 n = a073846_list !! (n-1)

%o a073846_list = concat $ transpose [a018252_list, a000040_list]

%o -- _Reinhard Zumkeller_, Jan 29 2014

%o (PARI) c(n) = for(k=0, primepi(n), isprime(n++)&&k--); n; \\ A002808

%o a(n) = if (n==1, 1, if (n%2, c(n\2), prime(n/2))); \\ _Michel Marcus_, Mar 06 2021

%o (Python)

%o from sympy import prime, composite

%o def A073846(n): return 1 if n == 1 else (composite(n//2) if n % 2 else prime(n//2)) # _Chai Wah Wu_, Mar 09 2021

%Y Cf. A002808, A018252, A000040, A261314.

%K easy,nonn

%O 1,2

%A _Amarnath Murthy_, Aug 14 2002

%E Edited by _Robert G. Wilson v_ and _Benoit Cloitre_, Aug 16 2002