login
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.
14
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
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
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
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