cp's OEIS Frontend

A348480 For numbers x_n coprime to 10 there exist infinitely many binary numbers b such that gcd(b,rev(b)) = x_n and digitsum(b) = x_n. a(n) is the smallest b converted to decimal that satisfies this constraint.

%I A348480 #58 Jan 11 2022 21:40:11
%S A348480 1,11,4399137296449,767,4543829,302306413101798081695809,1041919,
%T A348480 4120511,119471087,92239871,461373439,3221191679,25098711039,
%U A348480 5864072675327,2642508222647189060948556167549513,20016007615544303,208836273045503,70085007900671,985162418485119
%N A348480 For numbers x_n coprime to 10 there exist infinitely many binary numbers b such that gcd(b,rev(b)) = x_n and digitsum(b) = x_n. a(n) is the smallest b converted to decimal that satisfies this constraint.
%C A348480 Only for numbers x_n coprime to 10 (A045572, i.e., numbers ending with 1,3,7 or 9) do there exist binary numbers b such that gcd(b, rev(b)) = x_n and digitsum(b) = x_n. For the numbers 7 and 13 and the porous numbers 11, 37 and 101 (A337832), the terms in their binary form have more zeros than ones, which are called long solutions. In these cases, let e = mult_order(10, n), then b = 10^(e*n) + Sum_{i=0..n-2} 10^(e*i). For example, the multiplicative order of 10 mod 11 is 2 and 10001010101010101010101 is the solution. However, in the case of the porous number 121, this formula does not work because both b and rev(b) are divisible by 1111111111111111111111 which also has a multiplicative order of 10 = 22 like 121 and therefore two extra zeros need to be inserted.
%C A348480 For most numbers short solutions exist. Which numbers have a short solution and which have a long solution is still unclear.
%C A348480 For clarification: in gcd(1011,1101)=3 the two numbers 1011 and 1101 are base-10 numbers, but then 1011 is interpreted as a base-2 number and translated back to base 10 to get a(2)=11 (=8+2+1).
%H A348480 Ruediger Jehn, <a href="/A348480/b348480.txt">Table of n, a(n) for n = 1..54</a>
%H A348480 Rüdiger Jehn, <a href="https://youtu.be/w2sC1FSpmPA">A new 200 Euro math puzzle</a>, Youtube video, Sep 17 2021.
%H A348480 Rüdiger Jehn, <a href="https://arxiv.org/abs/2201.00710">Long Solutions of Sequence A348480 of the On-Line Encyclopedia of Integer Sequences</a>, arXiv:2201.00710 [math.GM], 2022.
%e A348480 x_2 = 3. a(2)=11 which in binary is 1011. gcd(1011,1101)=3 and there is no smaller binary number that satisfies this constraint.
%e A348480 x_4 = 9. a(4)=767 which in binary is 1011111111. gcd(1011111111,1111111101)=9 and there is no smaller binary number that satisfies this constraint.
%o A348480 (PARI) xx(n) = 2*n - 1 + (n+1)\4 * 2; \\ A045572
%o A348480 gcdr(n) = my(b=binary(n)); gcd(fromdigits(Vecrev(b), 10), fromdigits(b, 10));
%o A348480 a(n) = my(b=1, x=xx(n)); while ((hammingweight(b) != x) || (gcdr(b) != x), b++); b; \\ _Michel Marcus_, Dec 01 2021
%o A348480 (Python)
%o A348480 from sympy.utilities.iterables import multiset_permutations
%o A348480 from itertools import count
%o A348480 from math import gcd
%o A348480 def A348480(n):
%o A348480     if n == 1: return 1
%o A348480     xn = 2*(n+(n+1)//4) - 1
%o A348480     for l in count(xn-1):
%o A348480         for d in multiset_permutations(['0']*(l-xn+1)+['1']*(xn-1)):
%o A348480             s = '1'+''.join(d)
%o A348480             if gcd(int(s),int(s[::-1])) == xn:
%o A348480                 return int(s,2) # _Chai Wah Wu_, Jan 08 2022
%Y A348480 Cf. A045572, A333666, A337832, A350385.
%K A348480 nonn,base
%O A348480 1,2
%A A348480 _Ruediger Jehn_, Oct 20 2021
%E A348480 a(13) from _Giorgos Kalogeropoulos_, Oct 22 2021
%E A348480 a(14) from _Pontus von Brömssen_, Oct 23 2021
%E A348480 a(15) from _Ruediger Jehn_, Dec 01 2021
%E A348480 a(16) - a(29) from _Ruediger Jehn_, Dec 17 2021
%E A348480 a(30) - a(54) from _Ruediger Jehn_, Jan 11 2022