login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

a(n) is the least positive integer whose binary expansion is the concatenation of the binary expansions of two numbers whose product is n.
2

%I #17 Apr 07 2023 10:51:31

%S 3,5,7,9,11,11,15,17,15,21,23,19,27,23,23,33,35,27,39,37,31,43,47,35,

%T 45,45,39,39,59,43,63,65,47,69,47,51,75,77,55,69,83,55,87,75,63,87,95,

%U 67,63,85,71,77,107,75,91,71,79,93,119,79,123,95,79,129,93

%N a(n) is the least positive integer whose binary expansion is the concatenation of the binary expansions of two numbers whose product is n.

%C For any prime number p, a(p) is the least of the binary concatenation of p with 1 or the binary concatenation of 1 with p.

%H Michael De Vlieger, <a href="/A362022/b362022.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) <= 2*n + 1.

%F a(n) <= 2^A070939(n) + n.

%F a(n) = Min_{d | n} A163621(n/d, d).

%e The first terms, alongside their binary expansion split into two parts, are:

%e n a(n) bin(a(n))

%e -- ---- ---------

%e 1 3 1|1

%e 2 5 10|1

%e 3 7 11|1

%e 4 9 100|1

%e 5 11 101|1

%e 6 11 10|11

%e 7 15 111|1

%e 8 17 1000|1

%e 9 15 11|11

%e 10 21 1010|1

%e 11 23 1011|1

%e 12 19 100|11

%e 13 27 1101|1

%e 14 23 10|111

%e 15 23 101|11

%t Table[Min@ Map[FromDigits[Join @@ #, 2] &, Join @@ {#, Reverse /@ #}] &@ Map[IntegerDigits[#, 2] &, Transpose@{#, n/#}, {2}] &@ TakeWhile[Divisors[n], # <= Sqrt[n] &], {n, 60}] (* _Michael De Vlieger_, Apr 07 2023 *)

%o (PARI) a(n, base = 2) = { my (v = oo); fordiv (n, d, v = min(v, n/d * base^#digits(d, base) + d);); return (v); }

%o (Python)

%o from sympy import divisors

%o def a(n): return min(d+((n//d)<<d.bit_length()) for d in divisors(n))

%o print([a(n) for n in range(1, 66)]) # _Michael S. Branicky_, Apr 05 2023

%Y Cf. A070939, A163621, A362023 (decimal variant).

%K nonn,base

%O 1,1

%A _Rémy Sigrist_, Apr 05 2023