mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2012-05-26, 20:48   #12
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default

Quote:
Originally Posted by Raman View Post
Thus, it translates into
"Has the Collatz Conjecture been proved? Is it being true? It states that any starting number when repeatedly multiplied by three, and then added one, terminates in one. It appears to me that it is being very likely for this(it) to be true."

For example, for some starting number N, repeatedly iterating the 3x+1 function one can try out to prove off something
thereby establishing an upper bound result that the intermediate number value will not (cannot) go beyond N.2k at all.
Oops, sorry, a major correction please.

It states that if the number is odd, then multiply by 3, and then add 1,
if it is even, then divide by 2.
If this process is being continued again and again, then taking any starting number will eventually end in 1 always.

I think that it is not being very tough in order to prove this fact,

There are more being chances for this to be true, in turn
that's what I will feel it repeatedly, in fact

Quote:
Take any starting number. If it is odd, then multiply by three and then add one. If it is even, then divide by two. If this process is continued, every number will eventually terminate in one. I feel that it is very likely for this to be true. I think that it is very easy to prove this, as well.
முக்கியமான திருத்தம்

ஏதாவது எண்ணை எடுத்துக்கொண்டு தொடங்குங்கள். அதை ஒற்றைப்படையாக இருந்தால், மூன்றால் பெருக்கிவிட்டு, ஒன்றை சேருங்கள். இரட்டைப்படையாக இருந்தால், இரண்டால் வகுங்கள். இந்த செயலை தொடர்ந்தால், எல்லாம் எண்களும் எப்பொழுதும் இறுதியில் ஒன்றில் வந்து முடிவடையும் என்று இந்த ஊகம் குறிக்கிறது. நான் இதை உண்மையாக இருக்க அதிக வாய்ப்புகள் இருக்கிறது என்று நினைக்கிறேன். அது போல், இதை நிரூபிக்கவும் மிகவும் எளிதாக இருக்கும் என்று எனக்கு தோன்றுகிறது.

சரி?

Last fiddled with by Raman on 2012-05-26 at 21:12
Raman is offline   Reply With Quote
Old 2012-05-26, 21:16   #13
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Quote:
Originally Posted by Raman View Post
Oops, sorry, a major correction please.

It states that if the number is odd, then multiply by 3, and then add 1,
if it is even, then divide by 2.
If this process is being continued again and again, then taking any starting number will eventually end in 1 always.

I think that it is not being very tough in order to prove this fact,

There are more being chances for this to be true, in turn
that's what I will feel it repeatedly, in fact

முக்கியமான திருத்தம்

ஏதாவது எண்ணை எடுத்துக்கொண்டு தொடங்குங்கள். அதை ஒற்றைப்படையாக இருந்தால், மூன்றால் பெருக்கிவிட்டு, ஒன்றை சேருங்கள். இரட்டைப்படையாக இருந்தால், இரண்டால் வகுங்கள். இந்த செயலை தொடர்ந்தால், எல்லாம் எண்களும் எப்பொழுதும் இறுதியில் ஒன்றில் வந்து முடிவடையும் என்று இந்த ஊகம் குறிக்கிறது. நான் இதை உண்மையாக இருக்க அதிக வாய்ப்புகள் இருக்கிறது என்று நினைக்கிறேன். அது போல், இதை நிரூபிக்கவும் மிகவும் எளிதாக இருக்கும் என்று எனக்கு தோன்றுகிறது.

சரி?
If it was easy, someone would have done it.
Dubslow is offline   Reply With Quote
Old 2012-05-26, 21:23   #14
garambois
 
garambois's Avatar
 
"Garambois Jean-Luc"
Oct 2011
France

100010000012 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
There are serious problems with the proof of lemma 5 (2nd article) even for cases where m is prime. As I can see you are trying to determine the complementer event: if q==-1 mod m and q|n and q^2 doesn't divide n then m|sigma(n).

But there are cases you left out in the counting: let m=5 and 2^3|n and 2^4 doesn't divide n you can get that sigma(2^3)=15 divides sigma(n), so 5 also divides sigma(n) but 2==-1 mod 5 is not true.

For composites m there are much more problems with the proof.


You are wrong !
It's a problem because the demonstration is in french. And the translation on the forum is wrong.

If q divides n and q don't divide n^2 then :
If n=qA and q and A are coprime

Then :
sigma(n)=(1+q) sigma(A)

And because q==-1[m] then m will divide (q+1)
So m will divide sigma(n)

You have to take q==-1[m], it is written in the french demonstration.

Did you read the french demonstration or the english demonstration on the forum before posting this message ???

Jean-Luc
garambois is offline   Reply With Quote
Old 2012-05-26, 21:46   #15
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

I'm working on making a (hopefully half decent) translation of the first PDF. I don't understand the first sentence of the proof of theorem 1. "Soient k  2 e/qui vaut m Ak". What's the 'e/qui'? Does it mean something like "Let k>=2 _along with_ an m \in A_k"?

Another note: In the first paragraph, it defines A_k for all l >= 1, but I don't see an l in the definition of the set. (Also, I think there's a typo 'pout' -> 'pour' in there.)

Also, it's slow going because half the time is spent reproducing the tex.
Dubslow is offline   Reply With Quote
Old 2012-05-26, 22:21   #16
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5×17×19 Posts
Default

Quote:
Originally Posted by garambois View Post
It's a problem because the demonstration is in french. And the translation on the forum is wrong.
OK, your proof is correct, though not checked every line and my French is poor. But I understand your idea, its nice.
R. Gerbicz is offline   Reply With Quote
Old 2012-05-26, 23:19   #17
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default Here's a stab at translating the first PDF

http://www.aliquotes.com/Aliquote.pdf
I can't offer any commentary at all on the mathematics of it; I'm just a messenger (I still don't really understand the first sentence of the proof of Theorem 1.)

I'd be willing to translate the second PDF, but it might go faster if I didn't have to reproduce all the TeX... (hint hint )
Edit: It's much fancier. This might take a while, but it'll be an interesting challenge. Can I get access to the original *TeX please?

My last note is to be careful about super- and sub-scripts; this forum's TeX-renderer can't handle multiple nested levels of supers/subs very well. I'd recommend reading this simultaneously with the original PDF -- the su*s are clearer there.

-----------------------------------------------------------

Let p_k be the k-th prime number. Let t_1 = 2 and for all k \ge 1, let t_{k+1} = \phi\left(p^{t_k+1}_k\cdot(p_{k+1}-1)\right)-1 where \phi is the Euler function. For all l\ge1, let A_k = \left{m\quad |\quad for\quad all \quad1\le i\le k\quad val_p_i(m) = t_i\right} be the set of integers whose factorization starts with the "driver" p^{t_1}_1...p^{t_k}_k. Let s(m)=\sigma(m)-m.


Theorem 1 (Lenstra 76): For all k\ge2, if m\in A_k, then s(m) \in A_{k-1}.

Proof: Let k \ge 2 with m \in A_k. Then there exists a prime B \in \mathbb{N} with p_1,...,p_k such that m=p^{t_1}_1...p^{t_k}_kB. We note that s(m)=\sigma(p^{t_1}_1)...\sigma(p^{t_k}_k)B-p^{t_1}_1...p^{t_k}_kB. We show that for all 1\le i\le k-1, \sigma(p^{t_{i+1}}_{i+1}) is divisible by p^{t_i+1}_i. We have \sigma(p^{t_{i+1}}_{i+1})=\frac {p^{t_{i+1}+1}_{i+1}-1} {p_{i+1}-1} which in turn equals \frac {p^{\phi\left(p^{t_i+1}_i\cdot(p_{i+1}-1)\right)}_{i+1}-1} {p_{i+1}-1} by construction of t_{i+1}. Recall Fermat's little theorem: for all n \in \mathbb{N} and a such that gcd(a,n)=1 we have a^{\phi(n)}-1\equiv 0\quad mod\quad n. We apply the theorem with a=p_{i+1} and n=\left(p^{t_i+1}_i\cdot(p_{i+1}-1)\right) and we obtain p^{\phi\left(p^{t_i+1}_i\cdot(p_{i+1}-1)\right)}_{i+1}-1\equiv 0\quad mod\quad \left(p^{t_i+1}_i\cdot(p_{i+1}-1)\right), which is equivalent to p^{t_i+1}_i\quad |\quad \sigma(p^{t_{i+1}}_{i+1}). We directly deduce that val_p_i(s(m))=t_i. Thus s(m) \in A_{k-1}.


Corollary 1 (Garambois' 2nd conjecture): For all k>1 and all l\in \mathbb{N}, there exists an Aliquot sequence such that for l consecutive iterations, \frac {s(m)} {m} > k.

Proof: We use Mertens' formula \sum_{p\quad prime,\quad p\le x}\frac {1} {p}\quad \sim\quad log\quad log\quad x. In particular, \sum_{p\quad prime} \frac{1}{p} diverges and the product \prod_{p\quad prime}(1+\frac{1}{p}) goes to infinity. Therefore there exists an n \in \mathbb{N} such that \prod_{i=1}^{n}(1+\frac{1}{p_i})>k+1. We choose an element m_0 of A_{n+l}. By Lensta's theorem, the first l+1 iterations of the Aliquot sequence starting at m_0 are respectively in A_{n+l},\quad A_{n+l-1},...,A_n. Let k \in [0,l]; then m\quad:=s^k(m_0) is in A_{n+k} and thus can be written as p^{t_1}_1...p^{t_{n+k}}_{n+k}B for an integer B coprime to p_1,...,p_{n+k}. We have \frac {s(m)}{m}=\frac{\sigma(m)}{m}-1 and \frac{\sigma(m)}{m}=\frac{\sigma(B)}{B}\prod_{i=1}^{n+k}(1+\frac{1}{p_i}+...+\frac{1}{p^{t_i}_i})\quad\ge\quad \frac{\sigma(B)}{B}\prod_{i=1}^{n+k}(1+\frac{1}{p_i})\quad \ge\quad \frac{\sigma(B)}{B}\prod_{i=1}^n (1+\frac{1}{p_i}) which is larger than \frac{\sigma(B)}{B}(k+1) by our choice of n. Finally, \sigma(B) is the sum of the divisors of B, here including B, so \sigma(B)>B. Thus \frac{\sigma(m)}{m}>k+1, whence we conclude \frac{s(m)}{m}>k.

Last fiddled with by Dubslow on 2012-05-26 at 23:33
Dubslow is offline   Reply With Quote
Old 2012-05-26, 23:45   #18
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5×17×19 Posts
Default

Quote:
Originally Posted by Dubslow View Post
http://www.aliquotes.com/Aliquote.pdf
I can't offer any commentary at all on the mathematics of it; I'm just a messenger (I still don't really understand the first sentence of the proof of Theorem 1.)
Thanks for the translation! So val_{p_i}(m)=t_i means that the exact p_i power divisor of m is p_i^t_i. You give no definition just explaining it with the driver.

The proof is good, but if you know Lenstra's theorem then this proof is really triviality.
R. Gerbicz is offline   Reply With Quote
Old 2012-05-27, 05:36   #19
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default For those who don't know an ounce of French...

Title: "On the density of integers n divisible by a certain integer m such that m does not divide \sigma(n)-n."

1 Introduction

"The purpose of this paper is to present the proof of a theorem concerning the density of integers n divisible by a certain integer m such that m doesn't divide \sigma(n)-n. We will demonstrate that this density is null by giving the asymptotic density of these numbers n less than a real x."

Translator's note: Hmm.. there's some way to translate this that I'm missing. Asymptotic complexity?

2 Notations and Definitions

"In all of the following:
Let m be a fixed natural integer \ge3.
x and t will designate positive real numbers.
We define sum-of-divisors and sum-of-proper-divisors functions like so:
\begin{align}\sigma(n)=\sum_{d|k}d.\end{align}
And
\begin{align}\sigma^\prime(n)=\sigma(n)-n.\end{align}
and we also define the function \phi(n): Euler's totient function which counts the number of integers \le that are coprime to n."

TN: There's a typo: "et on défnit" -> "et on définit"

3 Theorem 1

"The (asymptotic) density of the integers n divisible by m such that m doesn't divide \sigma^\prime(n) ( =\sigma(n)-n) is null (0). Further, we give the following [asymptotic density]|[asymptotic complexity] for any sufficiently large real number x:

A_m(x)\quad := card\left{ n\le x\quad such\quad that\quad m|n\quad and\quad m\dagger\sigma^\prime(n)\right}=\mathcal{O}\left(\frac{x}{\left(\ln\ln x\right)^{\frac{1}{\phi(m)}}}\right).

TN: Sorry about the dagger, I couldn't find a "does not divide" symbol that the forum would render.
TN2: I guess I'll slowly translate the thing over the course of a few days or something, then copy and paste the tex into one post.

Last fiddled with by Dubslow on 2012-05-27 at 05:55 Reason: adding part 2
Dubslow is offline   Reply With Quote
Old 2012-05-27, 05:53   #20
firejuggler
 
firejuggler's Avatar
 
"Vincent"
Apr 2010
Over the rainbow

22×7×103 Posts
Default

As I said earlier, I shouldn't try to translate math-involving thing.
firejuggler is offline   Reply With Quote
Old 2012-05-27, 05:55   #21
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Quote:
Originally Posted by firejuggler View Post
As I said earlier, I shouldn't try to translate math-involving thing.
I don't understand the math either.
Quote:
Originally Posted by R. Gerbicz View Post
So val_{p_i}(m)=t_i means that the exact p_i power divisor of m is p_i^t_i. You give no definition just explaining it with the driver.
I assume you're talking to the OP?
Quote:
Originally Posted by R. Gerbicz View Post
The proof is good, but if you know Lenstra's theorem then this proof is really triviality.
I suppose that's why he called it a corollary

Last fiddled with by Dubslow on 2012-05-27 at 05:56
Dubslow is offline   Reply With Quote
Old 2012-05-27, 10:40   #22
garambois
 
garambois's Avatar
 
"Garambois Jean-Luc"
Oct 2011
France

100010000012 Posts
Default

Quote:
Originally Posted by garambois View Post
You are wrong !
It's a problem because the demonstration is in french. And the translation on the forum is wrong.

If q divides n and q^2 don't divide n then :
If n=qA and q and A are coprime

Then :
sigma(n)=(1+q) sigma(A)

And because q==-1[m] then m will divide (q+1)
So m will divide sigma(n)

You have to take q==-1[m], it is written in the french demonstration.

Did you read the french demonstration or the english demonstration on the forum before posting this message ???

Jean-Luc
I'm sorry but it was an error in the text !

Wrong (old post) :
If q divides n and q don't divide n^2 then :

Right :
If q divides n and q^2 don't divide n then :

Jean-Luc
garambois is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Broken aliquot sequences fivemack FactorDB 46 2021-02-21 10:46
Broken aliquot sequences schickel FactorDB 18 2013-06-12 16:09
poaching aliquot sequences... Andi47 FactorDB 21 2011-12-29 21:11
Asymptotic properties of Aliquot sequences Lothar Homework Help 1 2011-03-29 09:23
New article on aliquot sequences schickel mersennewiki 0 2008-12-30 07:07

All times are UTC. The time now is 12:28.


Tue Feb 7 12:28:48 UTC 2023 up 173 days, 9:57, 1 user, load averages: 1.25, 1.37, 1.32

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

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