login
The OEIS is supported by the many generous donors 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

%I #47 Jun 25 2019 17:31:06

%S 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,

%T 30,19,26,18,20,14,17,16,22,13,14,12,11,8,9,16,26,15,18,12,13,8,8,12,

%U 16,8,7,8,6,5,6,32,58,38,52,38,41,30,37,36,45,29,31

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

%H Robert Israel, <a href="/A220370/b220370.txt">Table of n, a(n) for n = 1..10000</a> (first 90 terms from Marko Riedel)

%H Marko Riedel, <a href="http://math.stackexchange.com/questions/253554">Asymptotics of the square indicator sum for subsequences of digits</a>

%e 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.

%p g :=

%p proc(n,flag)

%p option remember;

%p local dlist, ind, flind, sseq, len, sel, val, r, res;

%p dlist := convert(n, base, 2);

%p len := nops(dlist);

%p res := 0;

%p for ind from 0 to 2^len-1 do

%p sel := convert(ind, base, 2);

%p sseq := [];

%p for flind to nops(sel) do

%p if sel[flind] = 1 then

%p sseq := [op(sseq), dlist[flind]];

%p fi;

%p od;

%p val := add(sseq[k]*2^(k-1), k=1..nops(sseq));

%p if flag = 0 then

%p r := floor(sqrt(val));

%p if val>0 and r*r = val then

%p res := res+1;

%p fi;

%p else

%p r := floor(sqrt(val/2));

%p if val>0 and 2*r*r = val then

%p res := res+1;

%p fi;

%p fi;

%p od;

%p res;

%p end;

%p # Alternative

%p SubSequenceCount:= proc(P, T) option remember;

%p local t;

%p if length(T) < length(P) then return 0 fi;

%p if length(P) = 1 then return StringTools:-CountCharacterOccurrences(T,P) fi;

%p if P[1] = T[1] then t:= procname(P[2..-1],T[2..-1]) else t:= 0 fi;

%p t + procname(P,T[2..-1]);

%p end proc:

%p f:= proc(n) local B,k,t,C,j;

%p B:= convert(convert(n,binary),string);

%p t:= 0:

%p for k from 1 to isqrt(n) do

%p C:= convert(convert(k^2,binary),string);

%p t:= t + add(SubSequenceCount(cat("0"$j,C),B),j=0..length(B)-length(C));

%p od;

%p t;

%p end proc:

%p map(f, [$1..100]); # _Robert Israel_, Jun 25 2019

%o (C)

%o unsigned long isqrt(unsigned long n)

%o {

%o if(!n) return 0;

%o unsigned long a = 1, b = n, mid;

%o do {

%o mid = (a+b)/2;

%o if(mid*mid>n){

%o b = mid;

%o }

%o else{

%o a = mid;

%o }

%o } while(b-a>1);

%o return a;

%o }

%o unsigned long g(unsigned long n)

%o {

%o int bits[256], len = 0;

%o while(n>0){

%o bits[len++] = n%2;

%o n >>= 1;

%o }

%o unsigned long res = 0, ind;

%o for(ind=0; ind<(1<<len); ind++){

%o unsigned long varind = ind;

%o int subseq[256], srcpos=0, pos=0;

%o while(varind>0){

%o if(varind%2){

%o subseq[pos++] = bits[srcpos];

%o }

%o srcpos++;

%o varind >>= 1;

%o }

%o unsigned long val = 0;

%o int seqpos = 0;

%o while(seqpos<pos){

%o val += (1<<seqpos)*subseq[seqpos];

%o seqpos++;

%o }

%o unsigned long cs = isqrt(val);

%o if(val>0 && cs*cs == val){

%o res++;

%o }

%o }

%o return res;

%o }

%K nonn,base,look

%O 1,3

%A _Marko Riedel_, Dec 14 2012

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 08:13 EDT 2024. Contains 371265 sequences. (Running on oeis4.)