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