login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A220370 Number of nonzero squares that appear as a subsequences in the binary digits of n. 1
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

LINKS

Marko Riedel, Table of n, a(n) for n = 1..90

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;

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: A287958 A059896 A079542 * A291048 A022467 A169614

Adjacent sequences:  A220367 A220368 A220369 * A220371 A220372 A220373

KEYWORD

nonn,base

AUTHOR

Marko Riedel, Dec 14 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 20 21:27 EDT 2019. Contains 323426 sequences. (Running on oeis4.)