cp's OEIS Frontend

A248756 a(n) = smallest k such that a(n-k) and n have the same number of 1's in their binary expansions, or a(n) = n if no such k exists.

%I A248756 #26 Apr 17 2015 01:32:58
%S A248756 1,1,3,2,2,3,7,3,1,2,4,4,6,7,15,4,4,5,5,1,7,1,8,5,4,5,12,7,14,15,31,7,
%T A248756 6,1,3,1,5,6,9,1,9,10,13,1,15,1,16,6,6,7,6,2,8,9,24,6,12,13,28,15,30,
%U A248756 31,63,11,8,9,3,1,5,6,10,1,9,10,14,1,16,17,17
%N A248756 a(n) = smallest k such that a(n-k) and n have the same number of 1's in their binary expansions, or a(n) = n if no such k exists.
%C A248756 a(n) = n if and only if n is one less than a power of 2.
%C A248756 A257078(n) = smallest number m such that a(m) = n. - _Reinhard Zumkeller_, Apr 16 2015
%H A248756 Nathaniel Shar, <a href="/A248756/b248756.txt">Table of n, a(n) for n = 1..8192</a>
%e A248756 a(12) = 4. 12 has two 1's in its binary expansion. The previous entry in the sequence that has two 1's in its binary expansion is 3, which is a(8), so a(12) = 12-8 = 4.
%o A248756 (PARI) findk(va, n) = {hw = hammingweight(n); for (k=1, n-1, if (hammingweight(va[n-k]) == hw, return (k)););return (0);}
%o A248756 lista(nn) = {va = vector(nn); for (n=1, nn, k = findk(va, n); if (k==0, va[n] = n, va[n] = k); print1(va[n], ", "););} \\ _Michel Marcus_, Oct 15 2014
%o A248756 (Perl) my (@a, @mem);
%o A248756 $a[0] = 0;
%o A248756 sub listseq {
%o A248756   my $n = shift;
%o A248756   for (1..$n) {
%o A248756     my $s = digitsum($_);
%o A248756     my $last = $mem[$s]||0;
%o A248756     $a[$_] = $_-$last;
%o A248756     $mem[digitsum($_-$last)] = $_;
%o A248756   }
%o A248756   print "$_ $a[$_]\n" for 1..$n;
%o A248756 }
%o A248756 sub digitsum {
%o A248756   my $n = shift;
%o A248756   my $k = 0;
%o A248756   do {$k += ($n&1)} while $n >>= 1;
%o A248756   return $k;
%o A248756 } # _Nathaniel Shar_, Oct 15 2014
%o A248756 (Haskell)
%o A248756 a248756 n = a248756_list !! (n-1)
%o A248756 a248756_list = f 1 [] where
%o A248756    f x yvs = fst yw : f (x + 1) (yw:yvs) where
%o A248756      yw = g 1 yvs
%o A248756      g _ []          = (x, h)
%o A248756      g k ((z,w):zws) = if w == h then (k, a000120 k) else g (k + 1) zws
%o A248756      h = a000120 x
%o A248756 -- _Reinhard Zumkeller_, Apr 16 2015
%Y A248756 Cf. A000120, A007088.
%Y A248756  Cf. A257078.
%K A248756 nonn,hear,look
%O A248756 1,3
%A A248756 _Nathaniel Shar_, Oct 13 2014