A078350 Number of primes in {n, f(n), f(f(n)), ..., 1}, where f is the Collatz function defined by f(x) = x/2 if x is even; f(x) = 3x + 1 if x is odd.

0, 1, 3, 1, 2, 3, 6, 1, 6, 2, 5, 3, 3, 6, 4, 1, 4, 6, 7, 2, 1, 5, 4, 3, 7, 3, 25, 6, 6, 4, 24, 1, 7, 4, 3, 6, 7, 7, 11, 2, 25, 1, 8, 5, 4, 4, 23, 3, 7, 7, 6, 3, 3, 25, 24, 6, 8, 6, 11, 4, 5, 24, 20, 1, 7, 7, 9, 4, 3, 3, 22, 6, 25, 7, 2, 7, 6, 11, 11, 2, 5, 25, 24, 1, 1, 8, 9, 5, 10, 4, 20, 4, 3, 23, 20

Offset

1,3

Comments

Number of primes in the trajectory of n under the 3x+1 map (i.e., the number of primes until the trajectory reaches 1, including 2 once). - Benoit Cloitre, Dec 23 2002

a(A196871(n)) = 0. - Reinhard Zumkeller, Oct 08 2011

a(A181921(n)) = n and a(m) <> n for m < A181921(n). - Reinhard Zumkeller, Apr 03 2012

Links

T. D. Noe, Table of n, a(n) for n = 1..10000

J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.

Eric Weisstein's World of Mathematics, Collatz Problem

Wikipedia, Collatz conjecture

Index entries for sequences related to 3x+1 (or Collatz) problem

Formula

a(n) = A055509(n) + 1 for n > 1.

a(n) = 1 when n > 1 is in A000079, i.e., a power of 2. - Benoit Cloitre, Dec 20 2017

Example

3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1; in this trajectory 3, 5, 2 are primes hence a(3) = 3. - Benoit Cloitre, Dec 23 2002
The finite sequence n, f(n), f(f(n)), ..., 1 for n = 12 is 12, 6, 3, 10, 5, 16, 8, 4, 2, 1, which has three prime terms. Hence a(12) = 3.

Mathematica

f[n_] := n/2 /; Mod[n, 2] == 0 f[n_] := 3 n + 1 /; Mod[n, 2] == 1 g[n_] := Module[{i, p}, i = n; p = 0; While[i > 1, If[PrimeQ[i], p = p + 1]; i = f[i]]; p]; Table[g[n], {n, 1, 100}]
Table[Count[NestWhileList[If[EvenQ[#], #/2, 3#+1]&, n, #!=1&], _?PrimeQ], {n, 100}] (* Harvey P. Dale, Aug 29 2012 *)

Prog

(PARI) for(n=2, 500, s=n; t=0; while(s!=1, if(isprime(s)==1, t=t+1, t=t); if(s%2==0, s=s/2, s=(3*s+1)); if(s==1, print1(t, ", "); ); )) \\ Benoit Cloitre, Dec 23 2002
(PARI) a(n)=my(s=isprime(n)); while(n>1, if(n%2, n=(3*n+1)/2, n/=2); s+=isprime(n)); s \\ Charles R Greathouse IV, Apr 28 2015
(PARI) A078350(n, c=n>1)={while(1<n>>=valuation(n, 2), isprime(n)&&c++; n=n*3+1); c} \\ M. F. Hasler, Dec 05 2017
(Haskell) a078350 n = sum $ map a010051 $ takeWhile (> 1) $ iterate a006370 n  -- Reinhard Zumkeller, Oct 08 2011

Crossrefs

Cf. A064684, A006370, A010051.

Sequence in context: A245547 A138881 A070983 * A078719 A087227 A060477

Adjacent sequences: A078347 A078348 A078349 * A078351 A078352 A078353

Keyword

nonn,nice

Author

Joseph L. Pe, Dec 23 2002

Extensions

Edited by N. J. A. Sloane, Jan 17 2009 at the suggestion of R. J. Mathar

Status

approved