A344005 - OEIS

%I #83 Jan 21 2024 09:36:37

%S 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,

%T 5,30,31,11,16,14,8,36,18,12,15,40,6,42,11,9,22,46,15,48,24,17,12,52,

%U 26,10,7,18,28,58,15,60,30,27,63,25,11,66,16,23,14,70,8,72,36,24,19,21

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

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

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

%C a(n) = n-1 if n is a prime power. - _Chai Wah Wu_, Jun 04 2021

%C 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

%C Comment from _N. J. A. Sloane_, Jul 12 2021: (Start)

%C 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.

%C 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.

%C We can summarize these arguments as follows:

%C 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.

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

%C 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).

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

%D E. Bach and J. Shallit, Algorithmic Number Theory, Vol. 1: Efficient Algorithms, MIT Press, Cambridge, MA, 1996.

%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954.

%H Antti Karttunen, <a href="/A344005/b344005.txt">Table of n, a(n) for n = 1..10001</a> (first 10000 terms from Jon E. Schoenfield)

%H N. J. A. Sloane, <a href="/A344005/a344005.txt">Table of n, a(n) for n = 1..100000</a>

%H N. J. A. Sloane, <a href="/A344005/a344005_2.txt">Table of n, a(n) for n = 1..10^6</a>

%H N. J. A. Sloane, <a href="/A344005/a344005_10Million.gz">Table of n, a(n) for n = 1..10^7</a> (gzipped file)

%H N. J. A. Sloane, <a href="/A344005/a344005_1.txt">The Maple program Findm for computing a(n)</a>

%F a(n) = n - A182665(n). - _Antti Karttunen_, Jun 12 2022

%F a(n) = A345992(n) * A345998(n). - _Antti Karttunen_, Jan 21 2024

%p # To compute the first M terms, from _N. J. A. Sloane_, Jun 18 2021

%p with(NumberTheory);

%p M:=100000;

%p W:=Array(1..M,0);

%p W[1]:=1; W[2]:=1; Lo:=[1,2]; # divisors of m

%p for m from 2 to M do

%p Ln:=Divisors(m+1); # divisors of m+1

%p   for d1 in Lo do

%p     for d2 in Ln do

%p       d:=d1*d2;

%p       if d<=M and W[d]=0 then W[d]:=m; fi;

%p     od: # d2

%p   od: # d1

%p   Lo:=Ln;

%p od: # od m

%p WW:=[seq(W[i],i=1..100)];

%t Table[m=1;While[!Divisible[m(m+1),n],m++];m,{n,100}] (* _Giorgos Kalogeropoulos_, Jul 29 2021 *)

%t spm[n_]:=Module[{m=1},While[!Divisible[m(m+1),n],m++];m]; Array[spm,100] (* _Harvey P. Dale_, Dec 04 2022 *)

%o (PARI) a(n) = for(m=1, oo, if((m*(m+1))%n==0, return(m))) \\ _Felix Fröhlich_, Jun 04 2021

%o (Python 3.8+)

%o from itertools import combinations

%o from math import prod

%o from sympy import factorint

%o from sympy.ntheory.modular import crt

%o def A344005(n):

%o     if n == 1:

%o         return 1

%o     plist = [p**q for p, q in factorint(n).items()]

%o     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

%Y 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].

%Y See also A001221, A007875.

%K nonn

%O 1,3

%A _N. J. A. Sloane_, Jun 04 2021