OFFSET
1,3
LINKS
Robert Israel, Table of n, a(n) for n = 1..10000 (first 90 terms from Marko Riedel)
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
KEYWORD
AUTHOR
Marko Riedel, Dec 14 2012
STATUS
approved