login
A374843
Number of indices i in [n] such that in the trajectory of i for the Collatz (3x+1) problem the sum and the number of terms are coprime or the trajectory is not finite.
1
1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10, 11, 12, 12, 12, 13, 14, 14, 14, 14, 14, 15, 16, 17, 17, 18, 18, 19, 20, 21, 22, 22, 23, 23, 23, 24, 25, 26, 27, 28, 29, 30, 30, 31, 32, 33, 34, 35, 36, 37, 37, 38, 38, 39, 40, 40, 40, 40, 40, 40, 40, 40, 40, 41, 42, 43, 44, 45
OFFSET
1,2
COMMENTS
Terms in the trajectories for the Collatz (3x+1) problem can be used to approximate the value of Pi. This method was found by Roland Yéléhada (see the links below).
FORMULA
a(n) = a(n-1) + [gcd(A008908(n), A033493(n)) = 1] for n >= 1 with a(0) = 0, where [] is the Iverson bracket.
Limit_{n->oo} sqrt(6*n/a(n)) = Pi = A000796.
Limit_{n->oo} a(n)/n = A059956.
Limit_{n->oo} n/a(n) = A013661.
EXAMPLE
a(5) = 4 = 1 + 1 + 1 + 1 + 0, because gcd(1,1) = gcd(2,3) = gcd(8,49) = gcd(3,7) = 1 and gcd(6,36) > 1.
a(1000) = 606 -> sqrt(6*1000/a(1000)) = 3.14658387763... .
MAPLE
b:= proc(n) option remember; [n, 1]+
`if`(n=1, 0, b(`if`(n::even, n/2, 3*n+1)))
end:
a:= proc(n) option remember; `if`(n<1, 0,
a(n-1)+1-signum(igcd(b(n)[])-1))
end:
seq(a(n), n=1..68);
MATHEMATICA
b[n_] := b[n] = {n, 1} + If[n == 1, {0, 0}, b[If[EvenQ[n], n/2, 3*n + 1]]];
a[n_] := a[n] = If[n < 1, 0, a[n - 1] + 1 - Sign[GCD @@ b[n] - 1]];
Table[a[n], {n, 1, 68}] (* Jean-François Alcover, Sep 04 2024, after Alois P. Heinz *)
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jul 22 2024
STATUS
approved