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,4

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

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.

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 *)

Prog

(PARI) a(n)=sum(k=0, n, if(bitxor(n, k)<n&gcd(n, k)%2==1, 1, 0))

Crossrefs

Cf. A059029, A006257 (Josephus problem).

Sequence in context: A331924 A201582 A369881 * A376229 A127801 A096597

Adjacent sequences: A115376 A115377 A115378 * A115380 A115381 A115382

Keyword

nonn

Author

Paul D. Hanna, Jan 21 2006

Status

approved