cp's OEIS Frontend

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

%I A115379 #16 Sep 11 2024 00:30:32
%S A115379 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,
%T A115379 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,
%U A115379 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
%N A115379 Number of positive integers k < n such that n XOR k < n and gcd(n,k) is odd.
%C A115379 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.
%H A115379 Indranil Ghosh, <a href="/A115379/b115379.txt">Table of n, a(n) for n = 0..1000</a>
%H A115379 <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>
%F A115379 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.
%t A115379 Table[Sum[If[BitXor[n, k]< n && OddQ[GCD[n, k]], 1, 0], {k, 0, n}], {n, 0, 81}] (* _Indranil Ghosh_, Mar 16 2017 *)
%o A115379 (PARI) a(n)=sum(k=0,n,if(bitxor(n,k)<n&gcd(n,k)%2==1,1,0))
%Y A115379 Cf. A059029, A006257 (Josephus problem).
%K A115379 nonn
%O A115379 0,4
%A A115379 _Paul D. Hanna_, Jan 21 2006