cp's OEIS Frontend

A293975 If n is even, divide by 2; otherwise, add the next larger prime.

%I A293975 #20 Nov 08 2017 22:34:09
%S A293975 0,3,1,8,2,12,3,18,4,20,5,24,6,30,7,32,8,36,9,42,10,44,11,52,12,54,13,
%T A293975 56,14,60,15,68,16,70,17,72,18,78,19,80,20,84,21,90,22,92,23,100,24,
%U A293975 102,25,104,26,112,27,114,28,116,29,120,30,128,31,130,32,132,33,138,34
%N A293975 If n is even, divide by 2; otherwise, add the next larger prime.
%C A293975 Inspired by the "PrimeLatz" map A174221 (where the next three primes are added).
%C A293975 The trajectory under iterations of this map seems to end in the cycle 1 -> 3 -> 8 -> 4 -> 2 -> 1, for any starting value n. Can this be proved?
%C A293975 In order to develop a proof, one can consider the "condensed" version of the map which is: h(x) = odd_part(x+nextprime(x)); i.e., add the next prime, then remove all factors of 2. It is easy to see that this map verifies, for all x > 2, h(x) <= x + g(x)/2 where g(x) is the gap between the x and the next larger prime. Often, h(x) will be close to x/2 or even to x/4 or smaller. Nonetheless, for any power (iteration) of h, there are numbers for which h^m is increasing, e.g., h(h(h(x))) > x for x = 1, 525, 891, 1071, 1135, ..., and h^4(x) > x for x = 2, 1329, 5591, 8469, 9555, ...
%C A293975 From _Robert Israel_, Nov 08 2017: (Start)
%C A293975 It suffices to prove that if n > 1 is odd, the trajectory {x(i)} starting at x(0)=n contains some number < n.  Let p = nextprime(n).  As long as x(2k) is odd we have x(2k+1) = x(2k)+p and x(2k+2)=(x(2k)+p)/2 with
%C A293975 n <= x(2k) < x(2k+2) < p.  But this can only continue finitely many times: eventually x(2k) must be even, and then x(2k+1) < p/2 < n (by Bertrand's postulate). (End)
%H A293975 Robert Israel, <a href="/A293975/b293975.txt">Table of n, a(n) for n = 0..10001</a>
%p A293975 seq(op([k,2*k+1+nextprime(2*k+1)]),k=0..100); # _Robert Israel_, Nov 08 2017
%t A293975 Array[If[EvenQ@ #, #/2, NextPrime@ # + # &@ #] &, 69, 0] (* _Michael De Vlieger_, Nov 08 2017 *)
%o A293975 (PARI) A293975(n)=if(bittest(n,0),n+nextprime(n+1),n\2)
%Y A293975 Cf. A174221 (the "PrimeLatz" map), A006370 (the "3x+1" map).
%K A293975 nonn
%O A293975 0,2
%A A293975 _M. F. Hasler_, Nov 04 2017