cp's OEIS Frontend

A371641 The smallest composite number which divides the concatenation of its ascending ordered prime factors, with repetition, when written in base n.

%I A371641 #54 Jan 12 2025 14:56:53
%S A371641 85329,4,224675,4,1140391,4,9,4,28749,4,841,4,9,4,239571,4,343,4,9,4,
%T A371641 231,4,25,4,9,4,315,4,343,4,9,4,25,4,9761637601,4,9,4,4234329,4,715,4,
%U A371641 9,4,609,4,49,4,9,4,195,4,25,4,9,4,1015,4,76729,4,9,4,25,4,14332171
%N A371641 The smallest composite number which divides the concatenation of its ascending ordered prime factors, with repetition, when written in base n.
%C A371641 The number 4 = 2*2 in any base b = 3 + 2*n, n >= 0, will always divide the concatenation of its prime divisors as 4 = "2"_b + "2"_b = "22"_b = 2*(3 + 2*n) + 2 = 8 + 4*n, which is divisible by 4.
%C A371641 The number 9 = 3*3 in any base b = 8 + 6*n, n >= 0, will always divide the concatenation of its prime divisors as 9 = "3"_b + "3"_b = "33"_b = 3*(8 + 6*n) + 3 = 27 + 18*n, which is divisible by 9.
%C A371641 Theorem: if p is prime, then a(p*(m+2)-1) <= p^2 for all m >= 0. Proof: If p is prime and base b = p*(m+2)-1 for some m >= 0, then b > p and p expressed in base b = "p"_b and thus "pp"_b = p*(b+1) = p^2*(m+2), i.e., divisible by p^2. - _Chai Wah Wu_, Apr 01 2024
%C A371641 a(36) <= 9761637601. a(40) = 4234329. By the theorem above if n+1 is composite, then a(n) <= p^2 where p = A020639(n+1) is the smallest prime factor of n+1. The first few terms where the inequality is strict are: a(406) = 105, a(766) = 105, a(988) = 195, a(1036) = 105, a(1072) = 231, ... - _Chai Wah Wu_, Apr 11 2024
%C A371641 From _Chai Wah Wu_, Apr 12 2024: (Start)
%C A371641 Theorem: If n is even, then a(n) >= 9 is odd.
%C A371641 Proof: This is true for n = 2. Let n > 2 be even. Let m be even.
%C A371641 If m=2^k for k>1, then 2 concatenated k times in base n is 2*(n^(k-1)+...+n+1) = 2*(n^k-1)/(n-1).
%C A371641 Since n^k-1 is odd, m does not divide 2*(n^k-1)/(n-1). If m has an odd prime divisor then concatenating the primes in base n will result in an odd number that is not divisible by m.
%C A371641 Finally, a(n) >= 9 since the first odd composite number is 9. (End)
%H A371641 Michael S. Branicky, <a href="/A371641/b371641.txt">Table of n, a(n) for n = 2..129</a>
%e A371641 a(2) = 85329 as 85329 = 3_10 * 3_10 * 19_10 * 499_10 = 11_2 * 11_2 * 10011_2 * 111110011_2 = "111110011111110011"_2 = 255987_10 which is divisible by 85329.
%e A371641 a(10) = 28749 as 28749 =  3_10 * 7_10 * 37_10 * 37_10 = "373737"_10 = 373737_10 which is divisible by 28749. See also A259047.
%o A371641 (Python)
%o A371641 from itertools import count
%o A371641 from sympy.ntheory import digits
%o A371641 from sympy import factorint, isprime
%o A371641 def fromdigits(d, b):
%o A371641     n = 0
%o A371641     for di in d: n *= b; n += di
%o A371641     return n
%o A371641 def a(n):
%o A371641     for k in count(4):
%o A371641         if isprime(k): continue
%o A371641         sf = []
%o A371641         for p, e in factorint(k).items():
%o A371641             sf.extend(e*digits(p, n)[1:])
%o A371641         if fromdigits(sf, n)%k == 0:
%o A371641             return k
%o A371641 print([a(n) for n in range(2, 6)]) # _Michael S. Branicky_, Apr 01 2024
%o A371641 (Python)
%o A371641 from itertools import count
%o A371641 from sympy import factorint, integer_log
%o A371641 def A371641(n):
%o A371641     for m in count(4):
%o A371641         f = factorint(m)
%o A371641         if sum(f.values()) > 1:
%o A371641             c = 0
%o A371641             for p in sorted(f):
%o A371641                 a = pow(n,integer_log(p,n)[0]+1,m)
%o A371641                 for _ in range(f[p]):
%o A371641                     c = (c*a+p)%m
%o A371641             if not c:
%o A371641                 return m # _Chai Wah Wu_, Apr 11 2024
%o A371641 (PARI) has(F,n)=my(f=F[2],t); for(i=1,#f~, my(p=f[i,1],d=#digits(p,n),D=n^d); for(j=1,f[i,2], t=D*t+p)); t%F[1]==0
%o A371641 a(k,lim=10^6,startAt=4)=forfactored(n=startAt,lim, if(vecsum(n[2][,2])>1 && has(n,k), return(n[1]))); a(k,2*lim,lim+1) \\ _Charles R Greathouse IV_, Apr 11 2024
%Y A371641 Cf. A020639, A027746, A259047, A322843, A248915.
%K A371641 nonn,base
%O A371641 2,1
%A A371641 _Scott R. Shannon_, Mar 30 2024
%E A371641 a(36) and beyond from _Michael S. Branicky_, Apr 27 2024