|
%I #18 Sep 18 2017 09:25:55
%S 0,0,1,0,1,1,2,0,0,1,3,1,3,2,2,0,3,0,4,1,1,3,5,1,0,3,1,2,5,2,6,0,2,3,
%T 3,0,6,4,4,1,6,1,7,3,1,5,8,1,0,0,4,3,8,1,2,2,3,5,9,2,9,6,2,0,2,2,10,3,
%U 4,3,11,0,11,6,1,4,3,4,12,1,0,6,13,1,4,7,6,3,13,1,3,5,5,8,5,1,13,0,3,0,13,4,14,3,2
%N a(1) = 0, and for n > 1, a(n) = a(A252463(n)) + [n == 3 (mod 4)].
%C For numbers > 1, iterate the map x -> A252463(x) which divides even numbers by 2 and shifts every prime in the prime factorization of odd n one index step towards smaller primes. a(n) counts the numbers of the form 4k+3 encountered until 1 has been reached. The count includes also n itself if it is of the form 4k+3 (A004767).
%C In other words, locate the node which contains n in binary tree A005940 and traverse from that node towards the root, counting all numbers of the form 4k+3 that occur on the path.
%H Antti Karttunen, <a href="/A292377/b292377.txt">Table of n, a(n) for n = 1..16384</a>
%H <a href="/index/Pri#prime_indices">Index entries for sequences computed from indices in prime factorization</a>
%F a(1) = 0, and for n > 1, a(n) = a(A252463(n)) + floor((n mod 4)/3).
%F Equivalently, a(2n) = a(n), and for odd numbers n > 1, a(n) = a(A064989(n)) + [n == 3 (mod 4)].
%F a(n) = A000120(A292383(n)).
%F Other identities. For n >= 1:
%F a(n) >= A292376(n).
%F a(A000040(n)) = A267098(n).
%F 1 + a(n) - A292375(n) = A292378(n).
%F For n >= 2, a(n) + A292375(n) = A061395(n).
%t a[1] = 0; a[n_] := a[n] = a[Which[n == 1, 1, EvenQ@ n, n/2, True, Times @@ Power[Which[# == 1, 1, # == 2, 1, True, NextPrime[#, -1]] & /@ First@ #, Last@ #] &@ Transpose@ FactorInteger@ n]] + Boole[Mod[n, 4] == 3]; Array[a, 105]
%o (Scheme, with memoization-macro definec)
%o (definec (A292377 n) (if (= 1 n) 0 (+ (floor->exact (/ (modulo n 4) 3)) (A292377 (A252463 n)))))
%Y Cf. A000120, A005940, A061395, A064989, A252463, A292375, A292376, A292378, A292383.
%K nonn
%O 1,7
%A _Antti Karttunen_, Sep 17 2017
|
