A115379 Number of positive integers k < n such that n XOR k < n and gcd(n,k) is odd.

0, 1, 0, 3, 0, 3, 2, 7, 0, 3, 2, 7, 4, 11, 6, 15, 0, 3, 2, 7, 4, 11, 6, 15, 8, 19, 10, 23, 12, 27, 14, 31, 0, 3, 2, 7, 4, 11, 6, 15, 8, 19, 10, 23, 12, 27, 14, 31, 16, 35, 18, 39, 20, 43, 22, 47, 24, 51, 26, 55, 28, 59, 30, 63, 0, 3, 2, 7, 4, 11, 6, 15, 8, 19, 10, 23, 12, 27, 14, 31, 16, 35

Offset: 0

Author

Paul D. Hanna, Jan 21 2006

Keywords

• nonn

Comments

A059029 equals the limiting sequence of 2^k consecutive terms of this sequence starting at position 2^k as k increases, where A059029(n) = n if n is even, 2n+1 if n is odd.

Links

• Indranil Ghosh, Table of n, a(n) for n = 0..1000
• Index entries for sequences related to the Josephus Problem

Crossrefs

Cf. A059029, A006257 (Josephus problem).

Programs

Mathematica

Table[Sum[If[BitXor[n, k]< n && OddQ[GCD[n, k]], 1, 0], {k, 0, n}], {n, 0, 81}] (* Indranil Ghosh, Mar 16 2017 *)

PARI

a(n)=sum(k=0,n,if(bitxor(n,k)
				

Formula

a(2^n) = 0, a(2^n-1) = 2^n-1, for n >= 0. a(2^n+1)=3 (n>0), a(2^n+2)=2 (n>1), a(2^n+3)=7 (n>1), a(2^n+4)=4 (n>2), a(2^n+5)=11 (n>2), etc.