mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2018-02-27, 13:55   #1
JM Montolio A
 
Feb 2018

5×19 Posts
Smile A useful template for functions gcd() and totient().

For ANY function f(),

SUM( for i on [1,n] , of f(gcd(i,n) ) ) = SUM( for all d|n, of (f(d)*totient(n/d)) ).


great!

JM M

Last fiddled with by CRGreathouse on 2018-02-27 at 14:36 Reason: mcd -> gcd
JM Montolio A is offline   Reply With Quote
Old 2018-02-27, 15:02   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2×5×72×11 Posts
Default

If you'd stop calling your trivial observations "useful", you (and the forum) would be much better off.
VBCurtis is offline   Reply With Quote
Old 2018-02-27, 15:03   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

33×367 Posts
Default

I am nominating this user to have his own subforum.

JM Montolio A, - you are in luck! This forum has the special area for microblogs. Your posts will be perfect there.
Batalov is offline   Reply With Quote
Old 2018-02-27, 15:09   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,981 Posts
Default

Neat!
CRGreathouse is offline   Reply With Quote
Old 2018-02-27, 15:26   #5
JM Montolio A
 
Feb 2018

5·19 Posts
Default

JA JA!

But, backing to work, ¿ "the observation" is really trivial ?

JM M
JM Montolio A is offline   Reply With Quote
Old 2018-02-27, 16:13   #6
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

5·353 Posts
Default

It follows from proposition 11 and proposition 88/corollary 89 in our Number Theory Discussion group.
Nick is offline   Reply With Quote
Old 2018-02-27, 16:23   #7
JM Montolio A
 
Feb 2018

5F16 Posts
Default

Oh, sorry.

JM M
JM Montolio A is offline   Reply With Quote
Old 2018-02-28, 11:58   #8
JM Montolio A
 
Feb 2018

10111112 Posts
Smile -

proposition 11 and proposition 88/corollary 89

sorry, i think your work only is for f(m)=m.
I tested my "template" with many functions f().Look:

f(x)
-------------------------------------------
1 1 1*totient(N/d)
x mcd(N,i) d*totient(N/d)
N/x N/mcd(N,i) d*totient(d)
#d(x) #divisores(mcd(N,i))
#divisores(d)*totient(N/d)

sigma sigma(mcd(N,i))
sigma(d)*totient(N/d)

--------------------------------------------Nota.
#d():#nro. de divisores.
sigma():Suma de divisores.

Ejemplo. f(x)=x.
SUM mcd(N,i). SUM (d*totient(N/d)). -
n 1 s 1 t 1
n 2 s 3 t 3
n 3 s 5 t 5
n 4 s 8 t 8
n 5 s 9 t 9
n 6 s 15 t 15
n 7 s 13 t 13
n 8 s 20 t 20
n 9 s 21 t 21
n 10 s 27 t 27

Ejemplo. f(x)=(N/x).
SUM (N/mcd(N,i)). SUM(d*totient(d)).

n 1 s 1 t 1
n 2 s 3 t 3
n 3 s 7 t 7
n 4 s 11 t 11
n 5 s 21 t 21
n 6 s 21 t 21
n 7 s 43 t 43
n 8 s 43 t 43
n 9 s 61 t 61
n 10 s 63 t 63

Ejemplo. f(x)=#divisores(x).
SUM #divisores(mcd(N,i)).

SUM (#divisores(d)*totient(N/d)).
Sigma(N).
n 1 s 1 t 1 S 1
n 2 s 3 t 3 S 3
n 3 s 4 t 4 S 4
n 4 s 7 t 7 S 7
n 5 s 6 t 6 S 6
n 6 s 12 t 12 S 12
n 7 s 8 t 8 S 8
n 8 s 15 t 15 S 15
n 9 s 13 t 13 S 13
n 10 s 18 t 18 S 18

Ejemplo f(x)=sigma(x).
SUM sigma(mcd(N,i)).

SUM(sigma(d)*totient(N/d)).
#divisores(N).
n 1 s 1 t 1 1
n 2 s 4 t 4 2
n 3 s 6 t 6 2
n 4 s 12 t 12 3
n 5 s 10 t 10 2
n 6 s 24 t 24 4
n 7 s 14 t 14 2
n 8 s 32 t 32 4
n 9 s 27 t 27 3
n 10 s 40 t 40 4
--------------------------




JM Montolio A is offline   Reply With Quote
Old 2018-02-28, 15:23   #9
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

5·353 Posts
Default

Quote:
Originally Posted by JM Montolio A View Post
sorry, i think your work only is for f(m)=m.
I tested my "template" with many functions f().
There is no need to try different functions.
All you have to prove is that the number of times that the function is called with a particular parameter is the same on both sides of the equation.

The two key facts are:
1. for all positive integers a,b,d,n, we have gcd(a,b)=d if and only if gcd(na,nb)=nd.
2. for any positive integer n, the number of times that gcd(i,n)=1 as i runs from 0 to n-1 (or from 1 to n if you prefer it) is given by Euler's totient function \(\phi(n)\).
Nick is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Consecutive numbers not coprime to Euler's totient... carpetpool Miscellaneous Math 5 2017-03-09 05:45
C++ template function syntax issues ewmayer Programming 4 2013-04-13 17:45
Finding totient using discrete logarithm vector Miscellaneous Math 3 2007-11-20 18:50
euler's totient function toilet Math 1 2007-04-29 13:49
Busted functions Dougy Miscellaneous Math 4 2006-02-22 20:59

All times are UTC. The time now is 10:32.


Fri Aug 19 10:32:59 UTC 2022 up 1 day, 8:01, 0 users, load averages: 0.72, 0.89, 1.01

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔