A265008 Number of positive solutions to the equation A x B = C, where A, B and C are made from (contiguous) substrings of the binary representation of n.

1, 3, 3, 6, 5, 9, 5, 10, 8, 9, 9, 18, 13, 15, 7, 15, 12, 12, 13, 18, 11, 17, 13, 30, 23, 21, 17, 30, 21, 21, 9, 21, 17, 16, 16, 18, 16, 21, 17, 30, 22, 15, 17, 32, 21, 25, 19, 45, 34, 33, 27, 36, 25, 25, 25, 50, 37, 33, 27, 42, 33, 27, 11, 28, 23, 21, 21, 22, 20, 24, 20, 30, 20, 24, 23, 33, 27, 29, 21, 45, 34, 30, 29, 30, 17, 29, 25, 52, 40, 33, 25, 46, 31

Offset: 1

Author

Marko Riedel, Nov 29 2015

Keywords

• nonn
• base

Comments

Here all three of A, B and C are positive; if A and B are distinct then the solutions A X B = C and B X A = C are regarded as distinct; while A x A is counted once. A substring may be used any number of times.

Examples

			When n=6 = (110)_2 we get the substrings 1=(1)_2, 2=(10)_2, 3=(11)_2 and 6=(110)_2 with the products 1*1=1, 1*2=2, 2*1=2, 1*3=3, 3*1=3, 1*6=6, 6*1=6, 2*3=6, 3*2=6 for a total of 9. When n=8 = (1000)_2 we get the substrings 1=(1)_2, 2=(10)_2, 4=(100)_2 and 8=(1000)_2 with the products 1*1=1, 1*2=2, 2*1=2, 1*4=4, 4*1=4, 1*8=1, 8*1=1, 2*2=4, 2*4=8, 4*2=8 for a total of 10.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• Marko Riedel, Maple code for the number of solutions to A x B = C using binary substrings of n.

Crossrefs

Allowing A,B,C to be zero gives A265236.

See A265182, A265183 for decimal analogs.

Cf. A165416.

Programs

Haskell

a265008 n = length [() | let cs = a165416_row n, c <- cs,
            let as = takeWhile (<= c) cs, a <- as, b <- as, a * b == c]
-- Reinhard Zumkeller, Dec 05 2015

Maple

F:= proc(n) local L,ss;
  L:= convert(n,base,2);
  ss:= {seq(seq(add(2^(i-j)*L[i],i=j..k), j=1..k),k=1..nops(L))} minus {0};
  numboccur(true,[seq(seq(member(a*b,ss),a=ss),b=ss)]);
end proc:
seq(F(n), n=1..100); # Robert Israel, Nov 30 2015