A220370 Number of nonzero squares that appear as a subsequences in the binary digits of n.

1, 1, 2, 2, 3, 2, 3, 4, 7, 4, 5, 4, 4, 3, 4, 8, 15, 9, 12, 8, 9, 6, 7, 8, 11, 6, 6, 6, 5, 4, 5, 16, 30, 19, 26, 18, 20, 14, 17, 16, 22, 13, 14, 12, 11, 8, 9, 16, 26, 15, 18, 12, 13, 8, 8, 12, 16, 8, 7, 8, 6, 5, 6, 32, 58, 38, 52, 38, 41, 30, 37, 36, 45, 29, 31

Offset

1,3

Links

Robert Israel, Table of n, a(n) for n = 1..10000 (first 90 terms from Marko Riedel)

Marko Riedel, Asymptotics of the square indicator sum for subsequences of digits

Example

When n = 9 = (1001)_2, we obtain the following subsequences: (1)_2=1, (0)_2=0, (0)_2=0, (1)_2=1, (10)_2=2, (10)_2=2, (11)_2=3, (00)_2=0, (01)_2=1, (01)_2=1 and (100)_2=4, (101)_2=5, (101)_2=5, (001)_2=1, (1001)_2=9 and this includes seven nonzero squares, so a(9) = 7.

Maple

g :=
proc(n, flag)
        option remember;
        local dlist, ind, flind, sseq, len, sel, val, r, res;
        dlist := convert(n, base, 2);
        len := nops(dlist);
        res := 0;
        for ind from 0 to 2^len-1 do
            sel := convert(ind, base, 2);
            sseq := [];
            for flind to nops(sel) do
                if sel[flind] = 1 then
                   sseq := [op(sseq), dlist[flind]];
                fi;
            od;
            val := add(sseq[k]*2^(k-1), k=1..nops(sseq));
            if flag = 0 then
               r := floor(sqrt(val));
               if val>0 and r*r = val then
                  res := res+1;
               fi;
            else
               r := floor(sqrt(val/2));
               if val>0 and 2*r*r = val then
                  res := res+1;
               fi;
            fi;
        od;
        res;
end;
# Alternative
SubSequenceCount:= proc(P, T) option remember;
  local t;
  if length(T) < length(P) then return 0 fi;
  if length(P) = 1 then return StringTools:-CountCharacterOccurrences(T, P) fi;
  if P[1] = T[1] then t:= procname(P[2..-1], T[2..-1]) else t:= 0 fi;
  t + procname(P, T[2..-1]);
end proc:
f:= proc(n) local B, k, t, C, j;
  B:= convert(convert(n, binary), string);
  t:= 0:
  for k from 1 to isqrt(n) do
    C:= convert(convert(k^2, binary), string);
    t:= t + add(SubSequenceCount(cat("0"$j, C), B), j=0..length(B)-length(C));
  od;
  t;
end proc:
map(f, [$1..100]); # Robert Israel, Jun 25 2019

Prog

(C)
unsigned long isqrt(unsigned long n)
{
  if(!n) return 0;
  unsigned long a = 1, b = n, mid;
  do {
    mid = (a+b)/2;
    if(mid*mid>n){
      b = mid;
    }
    else{
      a = mid;
    }
  } while(b-a>1);
  return a;
}
unsigned long g(unsigned long n)
{
  int bits[256], len = 0;
  while(n>0){
    bits[len++] = n%2;
    n >>= 1;
  }
  unsigned long res = 0, ind;
  for(ind=0; ind<(1<<len); ind++){
    unsigned long varind = ind;
    int subseq[256], srcpos=0, pos=0;
    while(varind>0){
      if(varind%2){
        subseq[pos++] = bits[srcpos];
      }
      srcpos++;
      varind >>= 1;
    }
    unsigned long val = 0;
    int seqpos = 0;
    while(seqpos<pos){
      val += (1<<seqpos)*subseq[seqpos];
      seqpos++;
    }
    unsigned long cs = isqrt(val);
    if(val>0 && cs*cs == val){
      res++;
    }
  }
  return res;
}

Crossrefs

Sequence in context: A308630 A059896 A079542 * A291048 A022467 A306894

Adjacent sequences: A220367 A220368 A220369 * A220371 A220372 A220373

Keyword

nonn,base,look

Author

Marko Riedel, Dec 14 2012

Status

approved