Number Theory Challenge?

Question

1) Prove or disprove that every positive rational number can be represented as the finite sum of the reciprocals of distinct positive integers. Namely:

For any number m in Q+, there exists a finite sequence of distinct integers {a1, a2, a3, ...} such that m = 1/a1 + 1/a2 + 1/a3 + ...

2) Prove or disprove that for every positive rational number there exists a sequence satisfying the above conditions that is pairwise coprime. If it does exist, prove or disprove that the sequence is unique.

3) (Fun non-exactly-number-theory Bonus)

Recall the epsilon-delta definition of continuity (the names might be switched): A function f is continuous at a point x0 if for every ϵ > 0, there exists a number δ > 0 such that for all x, x-δ < x < x+δ, f(x0)-ϵ < f(x) < f(x0)+ϵ. Prove, by example, that there exists a function f : R --> R that is continuous at all the irrational numbers but discontinuous at all the rational numbers.

Update:

Thank you Buri for your contributions so far. Specifically, however:

1) Can you provide an algorithm, with proof, that will compute this sequence?

3) I am aware of Thomae's function - I was wondering if anyone had a function of their own to contribute.

Update 2:

@Northstar: Good reference, but you have only addressed the case where m < 1. Can the algorithm work for ANY positive rational number?

Buri · Accepted Answer

(1) follows easily from that fact that ∑ 1/k diverges.  I'm already familiar with this problem (I had to prove it for an Analysis problem set last year), so I won't provide a proof as to let others play around with it.

(2)  I'll take a look at it later today :) And I should probably get some rest before lol

(3) Thomae's function which is a standard example in a first year Analysis course:

http://en.wikipedia.org/wiki/Thomae%27s_function

=========
Addendum:  Sorry for the late addendum, but I've been really tight on time and so I'm only going to address (1).

To my surprise, this problem appears in Calculus by Spivak and he breaks down the problem the same way I proved it last year.  He gives this calculation as an illustration of the algorithm:

19/15 - 1/2 = 23/30
23/30 - 1/3 = 13/30
13/30 - 1/4 = 11/60
11/60 < 1/5 
11/60 - 1/6 = 1/60

Therefore, 19/15 = 1/2 + 1/3 + 1/4 + 1/6 + 1/60.

This is essentially Fibonacci's Method in Northstar's link.  
Spivak asks the reader to prove it works for x such that,

(**) 1/(n + 1) < x < 1/n 

To prove it for x > 1, there must exist an n ≥ 1 (i.e. by divergence of ∑ 1/k) such that,

1 + 1/2 + ... + 1/n ≤ x ≤ 1 + 1/2 + ... + 1/n + 1/(n + 1)

And we're pretty much done, if you can see how we can use (**)  ;)

Northstar · Answer

1) Prove or disprove that every positive rational number can be represented as the finite sum of the reciprocals of distinct positive integers. Namely:

For any number m in Q+, there exists a finite sequence of distinct integers {a1, a2, a3, ...} such that m = 1/a1 + 1/a2 + 1/a3 + ...
_________________

These are called Egyptian Fractions.

Here is a link that explains them, calculates them, and also provides a proof.

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fractions/egyptian.html

Take note of the so called Greedy Algorithm.

Here is a link that is just a calculator for the Greedy Algorithm.  It can calculate using larger numbers than the former link can handle.

http://www.hostsrv.com/webmaa/app1/MSP/webm1010/egypt

Anonymous · Answer

I even have been given 009. right here is my artwork: notice: i'm utilising = signs and indications to symbolize congruence signs and indications 2003^2002 mod 1000 = 3^2002 = (3^2)^1001 mod 1000 = 9^1001 = 9*9^1000 mod 1000 = 9*(9^5)^2 hundred mod 1000 = 9*(40 9)^2 hundred = 9*(40 9^5)^40 mod 1000 = 9*(249)^40 = 9*(249^2)^20 mod 1000 = 9 *(one million)^20 = 9 mod 1000

Trending News

Number Theory Challenge?

3 Answers