|
%I #76 Mar 22 2024 17:44:02
%S 1,3,0,6,0,28,0,66,36,496,0,276,0,8128,1631432881,120,0,300,0,528,0,
%T 38009927549623740385753,0,630,0,33550336,2172602007770041,8256,0,
%U 209628,0,3570,0,8589869056,0,2016,0,137438691328,0,3240,0,662976,0,2096128,41616
%N Smallest triangular number with exactly n divisors, or 0 if no such number exists.
%C a(p)=0 if p is an odd prime. If n is an odd composite number, then a(n) is a square; see A001110 for numbers that are both triangular and square. - Victoria A Sapko (vsapko(AT)frc.mass.edu), Sep 28 2007
%C From _Jon E. Schoenfield_, May 25 2014: (Start)
%C If n is an odd semiprime, then a triangular number t having exactly n divisors must be of the form t = p^(2r) * q^(2s) = (p^r * q^s)^2, where p and q are distinct primes (p < q) and r and s are positive integers such that (2r+1)*(2s+1) = n.
%C If t is the k-th triangular number k(k+1)/2, it can be factored as t = u * v where
%C u = k and v = (k+1)/2 if k is odd, or
%C u = k/2 and v = k+1 if k is even.
%C Since neither p nor q (each of which is greater than 1) can divide both k and (k+1)/2, or both k/2 and k+1, only four cases need to be considered:
%C Case 1: k is even, q^(2s) = k/2, p^(2r) = k+1
%C Case 2: k is even, p^(2r) = k/2, q^(2s) = k+1
%C Case 3: k is odd, q^(2s) = k, p^(2r) = (k+1)/2
%C Case 4: k is odd, p^(2r) = k, q^(2s) = (k+1)/2
%C These yield the following equations:
%C Case 1: 2 * q^(2s) + 1 = p^(2r)
%C Case 2: 2 * p^(2r) + 1 = q^(2s)
%C Case 3: 2 * p^(2r) - 1 = q^(2s)
%C Case 4: 2 * q^(2s) - 1 = p^(2r)
%C Case 1 can be ruled out: since q > p, q is odd, so 2 * q^(2s) + 1 == 3 (mod 16), but p^(2r) cannot be 3 (mod 16).
%C For a Case 2 solution, since q is odd, 2 * p^(2r) + 1 = q^(2s) == 1 (mod 8), so p^(2r) == 0 (mod 4), so p must be even. Therefore, p = 2, and we must satisfy the equation 2 * 2^(2r) + 1 = q^(2s), whose left-hand side, which is divisible by 3 for every nonnegative integer r, is thus the square of a prime iff it is 3^2. So r=1, q=3, and s=1, yielding t = 2^2 * 3^2 = 36, which is the smallest triangular number with exactly 9 divisors, so a(9)=36.
%C In Case 3, both p and q must be odd, and p^r must be a number w having the property that 2*w^2 - 1 is square (i.e., (q^s)^2); every such number w is in A001653 (1, 5, 29, 169, 985, ...), and the corresponding value of q^s = sqrt(2*w^2 - 1) is in A002315 (1, 7, 41, 239, 1393, ...). (Note that A001653 and A002315 are defined with offsets of 1 and 0, respectively, so A001653(j) corresponds to A002315(j-1).) However, for odd semiprime n > 9, we need r > 1 and/or s > 1. The only nontrivial power (i.e., number of the form x^m, where both x and m are integers greater than 2) in A001653 is A001653(4) = 169 = 13^2 [Pethö], so the only Case 3 solution with r > 1 is 2 * 13^4 - 1 = 239^2, which yields the 15-divisor triangular number 13^4 * 239^2 = 1631432881 = a(15). A Case 3 solution with r = 1 and s > 1 would require 2 * p^2 - 1 = q^(2s), which is impossible since p < q.
%C Finally, in Case 4, both p and q must be odd, q^s must be in A001653, and p^r must be the corresponding term in A002315. However, using the only nontrivial power in A001653 (i.e., 169 = 13^2) as q^s would not yield a valid solution here because it would mean p = 239 and q = 13 (contradicting p < q). Thus, if a Case 4 solution exists for odd semiprime n > 9, we must have s = 1 and r > 1, so n = (2r+1)*(2s+1) = (2r+1)*3, where 2r+1 is prime. Such a solution requires an index j satisfying two conditions: (1) A001653(j) = q^1 = q is prime, and (2) the corresponding term A002315(j-1) = p^r is a nontrivial prime power. There are no nontrivial powers (whether of primes or composites) among the terms in A002315 below 10^5000. Moreover, the terms in A001653 are the odd-indexed terms from A000129 (Pell numbers), so condition (1) requires that j satisfy A000129(2j-1) = q. A096650 lists the indices of all prime or probable prime Pell numbers up to 100000. A check of the value A002315(j-1) corresponding to each prime or probable prime among the odd-indexed Pell numbers A000129(2j-1) up to j=50000 determined that none were nontrivial powers, so if any Case 4 solution with n > 9 exists, it will yield a triangular number t = p^(2r) * q^2 = (2 * q^2 - 1) * q^2, where q >= A000129(100001) = 3.16...*10^38277, so t > 10^153110. Since there are no nontrivial powers at all in A002315 below 10^5000, and since prime Pell numbers above A000129(50000) seem so scarce, it seems extremely unlikely that any such solution exists.
%C Thus, a(n) = 0 for every odd semiprime n that is not divisible by 3, and assuming that no Case 4 solution for odd semiprime n > 9 exists, the only nonzero a(n) where n is an odd semiprime greater than 9 is a(15) = 13^4 * 239^2 = 1631432881.
%C If j is prime and n=2j, then a(n) (if nonzero) must be of the form p^r * q, where p and q are distinct primes, r = j-1, and q is one of 3 functions of p^r:
%C q = f1(p^r) = 2*p^r - 1
%C q = f2(p^r) = 2*p^r + 1
%C q = f3(p^r) = (p^r - 1)/2
%C Of these, q = f1(p^r) for all but two cases among n < 1000:
%C at n=362, q = f2(p^r), with p=3;
%C at n=514, q = f3(p^r), with p=331.
%C Conjecture: a(2j) > 0 for all j > 1. (This conjecture holds at least through n = 2j = 1000. The largest a(n) for even n <= 1000 is a(898) = 20599^448 * (2 * 20599^448 - 1) = 3.21...*10^3865.) (End)
%C For more known terms, and information about unknown terms, see Links. - _Jon E. Schoenfield_, May 26 2014
%C If d(k*(k+1)/2) = 21, note that 2*q^2 = p^6 + 1 = (p^2 + 1)*(p^4 - p^2 + 1) has no prime solutions, so then k = p^2 and k+1 = 2*q^6, where p and q are distinct primes. We can prove 2*x^3 - y^2 = 1 has only one positive solution (1, 1) which shows that p^2 + 1 = 2*q^6 has no prime solutions. In the ring of Gaussian integers, x^3 = (1+y*i)*(1-y*i)/((1+i)*(1-i)) and (1+y*i)/(1+i) is coprime to (1-y*i)/(1-i), thus (1+y*i)/(1+i) = (u+v*i)^3 and (1-y*i)/(1-i) = (u-v*i)^3 for some integers u and v. Note that 1+y*i = (1+i)*(u+v*i)^3 = (u+v)*(u^2+v^2-4*u*v) + (u-v)*(u^2+v^2+4*u*v)*i, we have (u+v)*(u^2+v^2-4*u*v) = 1. Therefore, u = 1 and v = 0 if u > v, which means y = (u-v)*(u^2+v^2+4*u*v) = 1. This implies that a(21) = 0. - _Jinyuan Wang_, Aug 22 2020
%C a(n) is a perfect number for all n such that n/2 is in A000043. - _J. Lowell_, Mar 16 2024
%H Attila Pethö, <a href="https://arato.inf.unideb.hu/petho.attila/cikkek/PELL2_44.pdf">The Pell sequence contains only trivial perfect powers</a>, Kossuth Lajos University, Department of Computer Science, H-4010 Debrecen, P.O. Box 12, Hungary, Dedicated to V.T. Sós and A. Hajnal, May 18 2008.
%H Project Euler, <a href="https://projecteuler.net/problem=12">Highly divisible triangular number</a>, Problem 12.
%H Jon E. Schoenfield, <a href="/A081978/a081978.txt">Table of n, a(n) for known terms in n = 1..100, with notes on unknown terms</a>
%e a(2)=3 because the smallest triangular number with 2 divisors is T(2)=3.
%Y Greedy inverse of A063440.
%Y Cf. A000129, A001110, A001653, A002315, A081979, A242585, A319037.
%K nonn,hard
%O 1,2
%A _Amarnath Murthy_, Apr 03 2003
%E More terms from Victoria A Sapko (vsapko(AT)frc.mass.edu), Sep 28 2007
%E a(14) corrected and a(20) added by _Jon E. Schoenfield_, May 11 2014
%E a(21)-a(24) from _Jinyuan Wang_, Aug 22 2020
%E a(25)-a(45) from _Jon E. Schoenfield_, Jan 28 2021
|
