0
$\begingroup$

Is there a common formula for this sequence?

gcd(1,n) * gcd(2,n) * ... * gcd(m,n)

for two positive integers n,m?

$\endgroup$

migrated from stackoverflow.com Aug 19 '16 at 11:58

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ I've made an OEIS sequence that enumerates this for n, m > 0: oeis.org/A276162 $\endgroup$ – Peter Kagey Nov 30 '16 at 18:46
0
$\begingroup$

We can look at the slightly simpler problem of gcd(1,n)*gcd(2,n)*....*gcd(n-1,n). Which is the sequence

1, 1, 1, 2, 1, 12, 1, 16, 9, 80, 1, 3456, 1, 448, 2025, 2048, 1, 186624, 1,

This has an entry in the Online Encyclopedia of Integer Sequences at OEIS A051190. I can't see any particularly simple formula for this listed but the related sequence OEIS A092287 can be considered a generation of factorials.

There is one obvious simplification of your problem. If m < n and n is prime then the result must be 1.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy