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.

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, 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, 31, 63, 11, 8, 9, 3, 1, 5, 6, 10, 1, 9, 10, 14, 1, 16, 17, 17

Offset

1,3

Comments

a(n) = n if and only if n is one less than a power of 2.

A257078(n) = smallest number m such that a(m) = n. - Reinhard Zumkeller, Apr 16 2015

Links

Nathaniel Shar, Table of n, a(n) for n = 1..8192

Example

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.

Prog

(PARI) findk(va, n) = {hw = hammingweight(n); for (k=1, n-1, if (hammingweight(va[n-k]) == hw, return (k)); ); return (0); }
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
(Perl) my (@a, @mem);
$a[0] = 0;
sub listseq {
  my $n = shift;
  for (1..$n) {
    my $s = digitsum($_);
    my $last = $mem[$s]||0;
    $a[$_] = $_-$last;
    $mem[digitsum($_-$last)] = $_;
  }
  print "$_ $a[$_]\n" for 1..$n;
}
sub digitsum {
  my $n = shift;
  my $k = 0;
  do {$k += ($n&1)} while $n >>= 1;
  return $k;
} # Nathaniel Shar, Oct 15 2014
(Haskell)
a248756 n = a248756_list !! (n-1)
a248756_list = f 1 [] where
   f x yvs = fst yw : f (x + 1) (yw:yvs) where
     yw = g 1 yvs
     g _ []          = (x, h)
     g k ((z, w):zws) = if w == h then (k, a000120 k) else g (k + 1) zws
     h = a000120 x
-- Reinhard Zumkeller, Apr 16 2015

Crossrefs

Cf. A000120, A007088.

Cf. A257078.

Sequence in context: A324465 A361565 A334592 * A059942 A032450 A376274

Adjacent sequences: A248753 A248754 A248755 * A248757 A248758 A248759

Keyword

nonn,hear,look

Author

Nathaniel Shar, Oct 13 2014

Status

approved