[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