Prev: The Goldbach Conjecture: is this statement true?
Next: A Collatz anomaly (3n+a)
From: Leroy Quet on 7 Jul 2010 15:17
This was very easily found, so it must be well known. Yet I have yet
to see it elsewhere.

(I already started another thread a few days ago on the specific case
where a(k) is the Mobius function.)

Let n and m be any positive integers where m divides n.

{a(k)} can be any sequence defined for 1 <= k <= n.

Then (unless I made an error, which is possible):

sum{j=1 to n} sum{k|GCD(j,n)} a(k) * cos(2 pi j/m) =

sum{k|(n/m)} a(n/k) * k,

which is interesting when m = n:

sum{j=1 to n} sum{k|GCD(j,n)} a(k) * cos(2 pi j/n) =

a(n),
for all positive integers n.

You can replace cos(2 pi j/m) and cos(2 pi j/n) with
exp(i 2 pi j/m) and exp(i 2 pi j/n), if you choose, of course.

Specific examples:

sum{j=1 to n} GCD(j,n) * cos(2 pi j/n) = phi(n),
the number of positive integers <= n and coprime to n.

If m divides n,
sum{j=1 to n} d(GCD(j,n)) * exp(i 2 pi j/m) = sigma(n/m),

where d(k) = the number of divisors of k, and sigma(k) = the sum of
the divisors of k.

Fun with easy math! Yay.

Thanks,
Leroy Quet

From: Rob Johnson on 8 Jul 2010 07:01
In article <4ecb94d3-4486-4e61-a55b-ab315f6be271(a)g19g2000yqc.googlegroups.com>,
Leroy Quet <qqquet(a)mindspring.com> wrote:
>This was very easily found, so it must be well known. Yet I have yet
>to see it elsewhere.
>
>(I already started another thread a few days ago on the specific case
>where a(k) is the Mobius function.)
>
>Let n and m be any positive integers where m divides n.
>
>{a(k)} can be any sequence defined for 1 <= k <= n.
>
>Then (unless I made an error, which is possible):
>
>sum{j=1 to n} sum{k|GCD(j,n)} a(k) * cos(2 pi j/m) =
>
>sum{k|(n/m)} a(n/k) * k,

I see no error.

n
--- ---
> > a(k) exp(i2pi j/m)
--- ---
j=1 k|(j,n)

k|(j,n) iff k|j and k|n; thus, we want to sum over all j and k so
that 1 <= j <= n, k|j, and k|n. Since j needs to be a multiple of
k, we can substitute, j -> jk and get 1 <= j <= n/k and k|n:

n/k
--- ---
= > > a(k) exp(i2pi jk/m)
--- ---
k|n j=1

if m does not divide k, then the inner sum is 0. Substitute, k -> km

n/m/k
--- ---
= > > a(km)
--- ---
k|n/m j=1

the term is independent of j, so we can replace the inner sum with
the term times the index count

---
= > n/m/k a(km)
---
k|n/m

substitute k -> n/m/k

---
= > k a(n/k)
---
k|n/m

Rob Johnson <rob(a)trash.whim.org>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
From: Leroy Quet on 9 Jul 2010 16:04
Leroy Quet wrote:
> This was very easily found, so it must be well known. Yet I have yet
> to see it elsewhere.
>
> (I already started another thread a few days ago on the specific case
> where a(k) is the Mobius function.)
>
> Let n and m be any positive integers where m divides n.
>
> {a(k)} can be any sequence defined for 1 <= k <= n.
>
> Then (unless I made an error, which is possible):
>
> sum{j=1 to n} sum{k|GCD(j,n)} a(k) * cos(2 pi j/m) =
>
> sum{k|(n/m)} a(n/k) * k,
>
> which is interesting when m = n:
>
> sum{j=1 to n} sum{k|GCD(j,n)} a(k) * cos(2 pi j/n) =
>
> a(n),
> for all positive integers n.
>
> You can replace cos(2 pi j/m) and cos(2 pi j/n) with
> exp(i 2 pi j/m) and exp(i 2 pi j/n), if you choose, of course.
>
> Specific examples:
>
> sum{j=1 to n} GCD(j,n) * cos(2 pi j/n) = phi(n),
> the number of positive integers <= n and coprime to n.
>
> If m divides n,
> sum{j=1 to n} d(GCD(j,n)) * exp(i 2 pi j/m) = sigma(n/m),
>
> where d(k) = the number of divisors of k, and sigma(k) = the sum of
> the divisors of k.
>
> Fun with easy math! Yay.
>


A consequence:

sum{k=1 to m} sum{j=1 to n} a(j) * d(GCD(j,k,m)) * cos(2pi k/m)
=
sum{j=1 to floor(n/m)} a(jm),

for all sequences {a(k)} defined for 1<=k<=n, and where d(m) is the
number of divisors of m.

This implies that, and is a consequence of,:

sum{k=1 to m} d(GCD(k,m,n)) cos(2p k/m) =

1 for m|n,
and = 0 for m does not divide n.

Also, it implies the specific result:

sum{k=1 to m} sum{j=1 to n} d(GCD(j,k,m)) * cos(2pi k/m)

= floor(n/m).

Sorry about the simplicity of all this. Gone are the days when I did
relatively tougher math.

Thanks,
Leroy Quet


From: Leroy Quet on 9 Jul 2010 17:39
Typo alert:

Should be:

This implies that, and is a consequence of,:
sum{k=1 to m} d(GCD(k,m,n)) cos(2 PI k/m) =
1 for m|n,
and = 0 for m does not divide n.

("pi", not "p".)

Thanks,
Leroy Quet
From: Leroy Quet on 11 Jul 2010 12:23
A specific case. (And I will cross-post this to another related
thread.)

m, n, and r are positive integers.
Let g = GCD(m,r).

If m|n and r|n, and if
GCD(n g /(m r), m /g) = 1,

then:

sum{1<=j<=n, GCD(j,n)=r} cos(2 pi j/m)

(= sum{1<=j<=n, GCD(j,n)=r} exp(i 2 pi j/m) )

= phi(n g/ (m r)) * mu(m/g),

where phi(k) is the number of positive integers <= k and coprime to k,
and where mu(k) is the Mobius function.

If m = n, we have the specific case:

sum{1<=j<=n, GCD(j,n)=r} cos(2 pi j/n)

= 0, if r doesn't divide n, of course,

= mu(n/r), if r|n.

Thanks,
Leroy Quet
 |  Next  |  Last
Pages: 1 2
Prev: The Goldbach Conjecture: is this statement true?
Next: A Collatz anomaly (3n+a)