wu :: forums « wu :: forums - Euler phi is DFT of GCD » Welcome, Guest. Please Login or Register. Feb 23rd, 2024, 6:17am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: Grimbal, william wu, Eigenray, SMQ, towr, Icarus)    Euler phi is DFT of GCD « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Euler phi is DFT of GCD  (Read 2271 times)
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Euler phi is DFT of GCD   « on: Jan 27th, 2009, 11:53am » Quote Modify

I saw this cute result on the Wikipedia:

(n) = k=1n  gcd(k,n) cos(2k/n)
 « Last Edit: Jan 30th, 2009, 12:05pm by Eigenray » IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Euler phi is DFT of GCD   « Reply #1 on: Jan 27th, 2009, 12:19pm » Quote Modify

"gcd" is missing in front of (k,n)
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
ThudnBlunder
Uberpuzzler

The dewdrop slides into the shining Sea

Gender:
Posts: 4489
 Re: Euler phi is DFT of GCD   « Reply #2 on: Jan 27th, 2009, 12:56pm » Quote Modify

on Jan 27th, 2009, 11:53am, Eigenray wrote:
 I saw this cute result on the Wikipedia:   (n) = k=1n  (k,n) cos(2k/n)

I saw this cute result elsewhere:

If (n)/n = 5/3 then 5n is an odd perfect number
where (n) is the sum of the divisors of the positive integer n, including 1 and n.

The idea crossed my mind to post it as a problem: Find an n such that (n)/n = 5/3
And then, after you had duly found one, to claim my 15 minutes of fame and fortune before you wised up. LOL

 « Last Edit: Jan 30th, 2009, 12:34pm by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
balakrishnan
Junior Member

Gender:
Posts: 92
 Re: Euler phi is DFT of GCD   « Reply #3 on: Jan 30th, 2009, 10:36am » Quote Modify

Here  is an interesting article.
 IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: Euler phi is DFT of GCD   « Reply #4 on: Jan 30th, 2009, 12:14pm » Quote Modify

on Jan 27th, 2009, 12:19pm, towr wrote:
 "gcd" is missing in front of (k,n)

I think it's clear from the context but if you insist...

on Jan 30th, 2009, 10:36am, balakrishnan wrote:
 Here  is an interesting article.

Unfortunately their forms use post requests so a direct link won't work.  Which one are you referring to?

Anyway, the result is not hard to prove; I only put it in this section because it seemed too abstract for a riddle.

Hint: What is the sum of all primitive m-th roots unity?
 IP Logged
balakrishnan
Junior Member

Gender:
Posts: 92
 Re: Euler phi is DFT of GCD   « Reply #5 on: Jan 30th, 2009, 12:42pm » Quote Modify

Oh, sorry: I was referring to ."The Fourier Transform of Functions of the Greatest Common Divisor "  by Wolfgang Schramm
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board