wu :: forums « wu :: forums - Euler phi is DFT of GCD » Welcome, Guest. Please Login or Register. Apr 25th, 2024, 1:26pm

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    putnam exam (pure math) (Moderators: william wu, Icarus, Grimbal, SMQ, towr, Eigenray)    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 2275 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