A344005 a(n) = smallest positive m such that n divides the oblong number m*(m+1).

1, 1, 2, 3, 4, 2, 6, 7, 8, 4, 10, 3, 12, 6, 5, 15, 16, 8, 18, 4, 6, 10, 22, 8, 24, 12, 26, 7, 28, 5, 30, 31, 11, 16, 14, 8, 36, 18, 12, 15, 40, 6, 42, 11, 9, 22, 46, 15, 48, 24, 17, 12, 52, 26, 10, 7, 18, 28, 58, 15, 60, 30, 27, 63, 25, 11, 66, 16, 23, 14, 70, 8, 72, 36, 24, 19, 21

Offset: 1

Author

N. J. A. Sloane, Jun 04 2021

Keywords

• nonn

Comments

a(n) <= A011772(n); equality holds if n is odd.

It appears that a(n) <= A047994(n).

a(n) = n-1 if n is a prime power. - Chai Wah Wu, Jun 04 2021

Theorem: a(n) <= n-1; a(n) = n-1 iff n is a prime power; if n is divisible by at least two different primes then a(n) <= n/2 - 1. a(n) >= (sqrt(4*n+1)-1)/2, with equality iff n is twice a triangular number. - N. J. A. Sloane, Jul 11 2021

Comment from N. J. A. Sloane, Jul 12 2021: (Start)

An efficient algorithm for a(n). Suppose a(n) = m. Since gcd(m,m+1) = 1. there are numbers X, Y >= 1 such that n = X*Y, X|m, and Y|m+1. Let m = u*X, m+1 = v*Y = u*X + 1, so u*X - v*Y = -1.

We can use the Euclidean algorithm to find u and v for a given factorization n = X*Y, except that there is ambiguity in the choice of (u,v), since we can add any multiple of (Y,X) to (u,v) to get other solutions. There is also the possibility that it would be better to have m+1 = u*X and m = v*Y, with u*X - v*Y = 1.

We can summarize these arguments as follows:

Theorem: m is the minimum of min(|u|*X, |v|*Y) over all factorizations n = X*Y with gcd(X,Y)=1 and u*X - v*Y = +-1.

The attached Maple program Findm computes m and returns a possible choice for X and Y.

The number of possible factorizations of n is 2^(omega(n)-1) - see A007875 and A001221. Since the average order of omega(n) is log log n (Hardy and Wright), this is about log n on the average. For a given pair X,Y, the Euclidean algorithm takes O(log n) word operations (not bit operations) [Bach and Shallit], so the overall complexity is O((log n)^2).

Note that we can always achieve |u| <= Y or |v| <= X by adding a suitable multiple of (Y,X) to (u,v). (End)

References

• E. Bach and J. Shallit, Algorithmic Number Theory, Vol. 1: Efficient Algorithms, MIT Press, Cambridge, MA, 1996.
• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954.

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10001 (first 10000 terms from Jon E. Schoenfield)
• N. J. A. Sloane, Table of n, a(n) for n = 1..100000
• N. J. A. Sloane, Table of n, a(n) for n = 1..10^6
• N. J. A. Sloane, Table of n, a(n) for n = 1..10^7 (gzipped file)
• N. J. A. Sloane, The Maple program Findm for computing a(n)

Crossrefs

Cf. A002378, A011772 and A345444 (bisections), A047994, A182665, A344006, A345983 (partial sums), A345988, A345992 [= gcd(a(n), n)], A345998, A346607 [= A047994(n)-a(n)], A346608 (where differs from A047994), A354875, A354918 (parity), A354919 (positions of odd terms), A354921 (where parity of a(n) differs from that of n), A354922 (where parity is same), A354924, A368698 [= a(Doudna(1+n)), see also A368693].

See also A001221, A007875.

Programs

Maple

# To compute the first M terms, from N. J. A. Sloane, Jun 18 2021
with(NumberTheory);
M:=100000;
W:=Array(1..M,0);
W[1]:=1; W[2]:=1; Lo:=[1,2]; # divisors of m
for m from 2 to M do
Ln:=Divisors(m+1); # divisors of m+1
  for d1 in Lo do
    for d2 in Ln do
      d:=d1*d2;
      if d<=M and W[d]=0 then W[d]:=m; fi;
    od: # d2
  od: # d1
  Lo:=Ln;
od: # od m
WW:=[seq(W[i],i=1..100)];

Mathematica

Table[m=1;While[!Divisible[m(m+1),n],m++];m,{n,100}] (* Giorgos Kalogeropoulos, Jul 29 2021 *)
spm[n_]:=Module[{m=1},While[!Divisible[m(m+1),n],m++];m]; Array[spm,100] (* Harvey P. Dale, Dec 04 2022 *)

PARI

a(n) = for(m=1, oo, if((m*(m+1))%n==0, return(m))) \\ Felix Fröhlich, Jun 04 2021
(Python 3.8+)
from itertools import combinations
from math import prod
from sympy import factorint
from sympy.ntheory.modular import crt
def A344005(n):
    if n == 1:
        return 1
    plist = [p**q for p, q in factorint(n).items()]
    return n-1 if len(plist) == 1 else int(min(min(crt([m,n//m],[0,-1])[0],crt([n//m,m],[0,-1])[0]) for m in (prod(d) for l in range(1,len(plist)//2+1) for d in combinations(plist,l)))) # Chai Wah Wu, Jun 04 2021

Formula

a(n) = n - A182665(n). - Antti Karttunen, Jun 12 2022

a(n) = A345992(n) * A345998(n). - Antti Karttunen, Jan 21 2024