[seqfan] Re: Binary Palindrome Subsequences
Richard Mathar
mathar at strw.leidenuniv.nl
Mon Dec 15 19:23:07 CET 2008
lq> Let a(n) = the number of distinct palindromic subsequences, each subsequence starting and ending with 1, that are contained in the binary representation of n.
lq>
lq> For most n, it seems, a(n) = A000120(n).
lq>
lq> (A000120(n) is the number of 1's digits in the binary representation of n.)
lq>
lq> But there are exceptions.
lq>
lq> For instance, 203 = 11001011 in binary.
lq>
lq> A000120(203) = 5, obviously.
lq>
lq> But I count 4 palindromic subsequences, each ending and starting with 1: 1, 11, 101, 1001.
lq>
lq> What is the sequence of positive integers n where a(n) does NOT = A000120(n).
lq>
lq> ....203, 211,...
lq>
lq> (I guess this sequence starts with 203, but I may have made an error.)
I get n, binary representation of n, number of bits set, and palindromic
subwords as follows:
203, [1, 1, 0, 1, 0, 0, 1, 1], 5, {1, 11, 101, 1001}
211, [1, 1, 0, 0, 1, 0, 1, 1], 5, {1, 11, 101, 1001}
333, [1, 0, 1, 1, 0, 0, 1, 0, 1], 5, {1, 11, 101, 1001}
357, [1, 0, 1, 0, 0, 1, 1, 0, 1], 5, {1, 11, 101, 1001}
395, [1, 1, 0, 1, 0, 0, 0, 1, 1], 5, {1, 11, 101, 10001}
406, [0, 1, 1, 0, 1, 0, 0, 1, 1], 5, {1, 11, 101, 1001}
407, [1, 1, 1, 0, 1, 0, 0, 1, 1], 6, {1, 11, 101, 111, 1001}
419, [1, 1, 0, 0, 0, 1, 0, 1, 1], 5, {1, 11, 101, 10001}
422, [0, 1, 1, 0, 0, 1, 0, 1, 1], 5, {1, 11, 101, 1001}
423, [1, 1, 1, 0, 0, 1, 0, 1, 1], 6, {1, 11, 101, 111, 1001}
459, [1, 1, 0, 1, 0, 0, 1, 1, 1], 6, {1, 11, 101, 111, 1001}
467, [1, 1, 0, 0, 1, 0, 1, 1, 1], 6, {1, 11, 101, 111, 1001}
601, [1, 0, 0, 1, 1, 0, 1, 0, 0, 1], 5, {1, 11, 101, 1001}
617, [1, 0, 0, 1, 0, 1, 1, 0, 0, 1], 5, {1, 11, 101, 1001}
653, [1, 0, 1, 1, 0, 0, 0, 1, 0, 1], 5, {1, 11, 101, 10001}
666, [0, 1, 0, 1, 1, 0, 0, 1, 0, 1], 5, {1, 11, 101, 1001}
667, [1, 1, 0, 1, 1, 0, 0, 1, 0, 1], 6, {1, 11, 101, 1001, 11011}
669, [1, 0, 1, 1, 1, 0, 0, 1, 0, 1], 6, {1, 11, 101, 111, 1001}
709, [1, 0, 1, 0, 0, 0, 1, 1, 0, 1], 5, {1, 11, 101, 10001}
714, [0, 1, 0, 1, 0, 0, 1, 1, 0, 1], 5, {1, 11, 101, 1001}
715, [1, 1, 0, 1, 0, 0, 1, 1, 0, 1], 6, {1, 11, 101, 1001}
723, [1, 1, 0, 0, 1, 0, 1, 1, 0, 1], 6, {1, 11, 101, 1001, 101101}
741, [1, 0, 1, 0, 0, 1, 1, 1, 0, 1], 6, {1, 11, 101, 111, 1001}
779, [1, 1, 0, 1, 0, 0, 0, 0, 1, 1], 5, {1, 11, 101, 100001}
787, [1, 1, 0, 0, 1, 0, 0, 0, 1, 1], 5, {1, 11, 1001, 10001}
790, [0, 1, 1, 0, 1, 0, 0, 0, 1, 1], 5, {1, 11, 101, 10001}
791, [1, 1, 1, 0, 1, 0, 0, 0, 1, 1], 6, {1, 11, 101, 111, 10001}
803, [1, 1, 0, 0, 0, 1, 0, 0, 1, 1], 5, {1, 11, 1001, 10001}
811, [1, 1, 0, 1, 0, 1, 0, 0, 1, 1], 6, {1, 11, 101, 1001, 10101}
812, [0, 0, 1, 1, 0, 1, 0, 0, 1, 1], 5, {1, 11, 101, 1001}
813, [1, 0, 1, 1, 0, 1, 0, 0, 1, 1], 6, {1, 11, 101, 1001, 101101}
814, [0, 1, 1, 1, 0, 1, 0, 0, 1, 1], 6, {1, 11, 101, 111, 1001}
815, [1, 1, 1, 1, 0, 1, 0, 0, 1, 1], 7, {1, 11, 101, 111, 1001, 1111}
835, [1, 1, 0, 0, 0, 0, 1, 0, 1, 1], 5, {1, 11, 101, 100001}
838, [0, 1, 1, 0, 0, 0, 1, 0, 1, 1], 5, {1, 11, 101, 10001}
839, [1, 1, 1, 0, 0, 0, 1, 0, 1, 1], 6, {1, 11, 101, 111, 10001}
844, [0, 0, 1, 1, 0, 0, 1, 0, 1, 1], 5, {1, 11, 101, 1001}
845, [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], 6, {1, 11, 101, 1001}
846, [0, 1, 1, 1, 0, 0, 1, 0, 1, 1], 6, {1, 11, 101, 111, 1001}
847, [1, 1, 1, 1, 0, 0, 1, 0, 1, 1], 7, {1, 11, 101, 111, 1001, 1111}
851, [1, 1, 0, 0, 1, 0, 1, 0, 1, 1], 6, {1, 11, 101, 1001, 10101}
869, [1, 0, 1, 0, 0, 1, 1, 0, 1, 1], 6, {1, 11, 101, 1001, 11011}
907, [1, 1, 0, 1, 0, 0, 0, 1, 1, 1], 6, {1, 11, 101, 111, 10001}
918, [0, 1, 1, 0, 1, 0, 0, 1, 1, 1], 6, {1, 11, 101, 111, 1001}
919, [1, 1, 1, 0, 1, 0, 0, 1, 1, 1], 7, {1, 11, 101, 111, 1001}
931, [1, 1, 0, 0, 0, 1, 0, 1, 1, 1], 6, {1, 11, 101, 111, 10001}
934, [0, 1, 1, 0, 0, 1, 0, 1, 1, 1], 6, {1, 11, 101, 111, 1001}
935, [1, 1, 1, 0, 0, 1, 0, 1, 1, 1], 7, {1, 11, 101, 111, 1001}
971, [1, 1, 0, 1, 0, 0, 1, 1, 1, 1], 7, {1, 11, 101, 111, 1001, 1111}
979, [1, 1, 0, 0, 1, 0, 1, 1, 1, 1], 7, {1, 11, 101, 111, 1001, 1111}
1202, [0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1], 5, {1, 11, 101, 1001}
1203, [1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1], 6, {1, 11, 101, 1001, 110011}
1209, [1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1], 6, {1, 11, 101, 111, 1001}
1227, [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1], 6, {1, 11, 101, 1001, 10011001}
1234, [0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1], 5, {1, 11, 101, 1001}
1235, [1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1], 6, {1, 11, 101, 1001}
1257, [1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1], 6, {1, 11, 101, 111, 1001}
1293, [1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1], 5, {1, 11, 101, 100001}
1306, [0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1], 5, {1, 11, 101, 10001}
1307, [1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1], 6, {1, 11, 101, 10001, 11011}
1309, [1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1], 6, {1, 11, 101, 111, 10001}
1332, [0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1], 5, {1, 11, 101, 1001}
1333, [1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1], 6, {1, 11, 101, 1001, 10101}
1334, [0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1], 6, {1, 11, 101, 1001, 11011}
Mapl'ish:
# check for palindromic subword starting with 1
ispal := proc(L)
local i ;
if nops(L) < 1 then
RETURN(false) ;
fi;
if op(1,L) <> 1 then
RETURN(false) ;
fi;
for i from 1 to nops(L)/2 do
if op(i,L) <> op(-i,L) then
RETURN(false) ;
fi;
od:
RETURN(true) ;
end:
# convert L into base 10 rep
L2bin := proc(L)
local i ;
add(op(i,L)*10^(i-1),i=1..nops(L)) ;
end:
# dissect binary rep into all subsequences
apal := proc(n)
local ps,dgs,s,s1,subl ;
ps := {} ;
dgs := convert(n,base,2) ;
for s from 1 to nops(dgs) do
for s1 from s to nops(dgs) do
subl := [op(s..s1,dgs)] ;
if ispal( subl ) then
ps := ps union { L2bin(subl) }
fi;
od:
od:
RETURN(ps) ;
end:
# A000120
ndgs := proc(n)
dgs := convert(n,base,2) ;
add(i,i=dgs) ;
end:
for n from 1 do
set1 := ndgs(n) ;
pals := apal(n) ;
if set1 <> nops(pals) then
print(n,convert(n,base,2),set1,pals) ;
fi;
od:
More information about the SeqFan
mailing list