cp's OEIS Frontend

A215199 Smallest number k such that k and k+1 are both of the form p*q^n where p and q are distinct primes.

%I A215199 #54 Aug 16 2025 21:15:30
%S A215199 14,44,135,2511,8991,29888,916352,12393728,155161088,2200933376,
%T A215199 6856828928,689278976,481758175232,3684603215871,35419114668032,
%U A215199 2035980763136,174123685117952,9399153082499072,19047348965998592,203368956137832447,24217192574746623,2503092614937444351
%N A215199 Smallest number k such that k and k+1 are both of the form p*q^n where p and q are distinct primes.
%C A215199 a(15) <= 35419114668032. - _Donovan Johnson_, Aug 22 2012
%C A215199 If k is a term such that k = p*q^n and k+1 = r*s^n, where p,q,r,s are primes, then clearly q != s. Conjecture: q and s are either 2 or 3 for all terms. - _Chai Wah Wu_, Mar 10 2019
%C A215199 Since q^n and s^n are coprime, the Chinese Remainder Theorem can be used to find candidate terms to test, i.e., numbers k such that k+1 == 0 (mod s^n) and k+1 == 1 (mod q^n) (see Python code). - _Chai Wah Wu_, Mar 12 2019
%C A215199 From _David A. Corneth_, Mar 13 2019: (Start)
%C A215199 Conjecture: Let 1 <= D < 2^n be the denominator of N/D of (3/2)^n. Without loss of generality, if the conjecture above holds that (q, s) = (2, 3) then r = D + k*2^n for some n.
%C A215199 Example: for n = 100, we have the continued fraction of (3/2)^100 to be 406561177535215237, 2, 1, 1, 14, 9, 1, 1, 2, 2, 1, 4, 1, 2, 6, 5, 1, 195, 3, 26, 39, 6, 1, 1, 1, 2, 7, 1, 4, 2, 1, 11, 1, 25, 6, 1, 4, 3, 2, 112, 1, 2, 1, 3, 1, 3, 4, 8, 1, 1, 12, 2, 1, 3, 2, 2 from which we compute D = 519502503658624787456021964081. We find r = 1100840223501761745286594404230449 = D + 868 * 2^100 giving a(100) + 1 = r*3^100. (End)
%H A215199 Chai Wah Wu, <a href="/A215199/b215199.txt">Table of n, a(n) for n = 1..1279</a> (terms 25..32 from David A. Corneth)
%e A215199 a(3) = 135 because 135 = 5*3^3 and 136 = 17*2^3;
%e A215199 a(4) = 2511 because 2511 = 31*3^4 and 2512 = 157*2^4.
%p A215199 psig := proc(n)
%p A215199     local s,p ;
%p A215199     s := [] ;
%p A215199     for p in ifactors(n)[2] do
%p A215199         s := [op(s),op(2,p)] ;
%p A215199     end do:
%p A215199     sort(s) ;
%p A215199 end proc:
%p A215199 A215199 := proc(n)
%p A215199     local slim,smi,sma,ca,qi,q,p,k ;
%p A215199     for slim from 0 do
%p A215199         smi := slim*1000 ;
%p A215199         sma := (slim+1)*1000 ;
%p A215199         ca := sma ;
%p A215199         q := 2 ;
%p A215199         for qi from 1 do
%p A215199             p := nextprime(floor(smi/q^n)-1) ;
%p A215199             while p*q^n < sma do
%p A215199                 if p <> q then
%p A215199                     k := p*q^n ;
%p A215199                     if psig(k+1) = [1,n] then
%p A215199                         ca := min(ca,k) ;
%p A215199                     end if;
%p A215199                 end if;
%p A215199                 p := nextprime(p) ;
%p A215199             end do:
%p A215199             if q^n >= sma then
%p A215199                 break;
%p A215199             end if;
%p A215199             q := nextprime(q) ;
%p A215199         end do:
%p A215199         if ca < sma then
%p A215199             return ca ;
%p A215199         end if;
%p A215199     end do:
%p A215199 end proc:
%p A215199 for n from 1 do
%p A215199     print(A215199(n)) ;
%p A215199 end do; # _R. J. Mathar_, Aug 07 2012
%o A215199 (Python)
%o A215199 from sympy import isprime, nextprime
%o A215199 from sympy.ntheory.modular import crt
%o A215199 def A215199(n):
%o A215199     l = len(str(3**n))-1
%o A215199     l10, result = 10**l, 2*10**l
%o A215199     while result >= 2*l10:
%o A215199         l += 1
%o A215199         l102, result = l10, 20*l10
%o A215199         l10 *= 10
%o A215199         q, qn = 2, 2**n
%o A215199         while qn <= l10:
%o A215199             s, sn = 2, 2**n
%o A215199             while sn <= l10:
%o A215199                 if s != q:
%o A215199                     a, b = crt([qn,sn],[0,1])
%o A215199                     if a <= l102:
%o A215199                         a = b*(l102//b) + a
%o A215199                     while a < l10:
%o A215199                         p, t = a//qn, (a-1)//sn
%o A215199                         if p != q and t != s and isprime(p) and isprime(t):
%o A215199                             result = min(result,a-1)
%o A215199                         a += b
%o A215199                 s = nextprime(s)
%o A215199                 sn = s**n
%o A215199             q = nextprime(q)
%o A215199             qn = q**n
%o A215199     return result # _Chai Wah Wu_, Mar 12 2019
%Y A215199 Cf. A074172, A215173, A215197, A215198.
%K A215199 nonn
%O A215199 1,1
%A A215199 _Michel Lagneau_, Aug 05 2012
%E A215199 a(10)-a(14) from _Donovan Johnson_, Aug 22 2012
%E A215199 a(15)-a(17) from _Chai Wah Wu_, Mar 09 2019
%E A215199 a(18)-a(22) from _Chai Wah Wu_, Mar 10 2019