mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2017-02-27, 14:39   #1
mickfrancis
 
Apr 2014
Marlow, UK

708 Posts
Default Finding multiples of a real number that are close to a whole number

Given a real number r, and a small positive value e arbitrarily close to 0, does anyone know of a fast way to find integer multipliers m such that either:
{mr} < e
or
1 - {mr} < e
(where {mr} is the fractional part of mr)

Thanks in advance for any help,

Mick.
mickfrancis is offline   Reply With Quote
Old 2017-02-27, 15:08   #2
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

3·19·113 Posts
Default

The search term you want is "continued fractions"
fivemack is offline   Reply With Quote
Old 2017-02-27, 15:20   #3
mickfrancis
 
Apr 2014
Marlow, UK

5610 Posts
Default

Quote:
Originally Posted by fivemack View Post
The search term you want is "continued fractions"
Thanks for the response. I'm afraid you'll have to forgive my ignorance, but I can't see at the moment how continued fractions help me here - any hints appreciated.

Mick.
mickfrancis is offline   Reply With Quote
Old 2017-02-27, 15:33   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

3×19×113 Posts
Default

Quote:
Originally Posted by mickfrancis View Post
Thanks for the response. I'm afraid you'll have to forgive my ignorance, but I can't see at the moment how continued fractions help me here - any hints appreciated.

Mick.
Write R as a continued fraction, compute the convergents, and the denominator of a convergent sufficiently far along the list will be a usable M - roughly, and there are various O(1) factors here which you probably want to look up in Hardy & Wright, if D is the denominator of a continued fraction convergent then DR will be within about 1/D of an integer.

Code:
default(realprecision,500)
p=Pi()
M=contfracpnqn(contfrac(p,21)) 
M[2,1]*p
If you want a worst-case term, there's a nice theorem that phi = (1+sqrt(5))/2 is the hardest number to approximate with continued fractions, and the nth denominator of the continued fraction of phi is the nth Fibonacci number. So if you take your epsilon, and let n be the index of the first Fibonacci number larger than the reciprocal of epsilon, the denominator of the nth continued fraction convergent of R will definitely be a usable multiplier.

Last fiddled with by fivemack on 2017-02-27 at 15:33
fivemack is offline   Reply With Quote
Old 2017-02-27, 15:51   #5
mickfrancis
 
Apr 2014
Marlow, UK

23·7 Posts
Default

Quote:
Originally Posted by fivemack View Post
Write R as a continued fraction, compute the convergents, and the denominator of a convergent sufficiently far along the list will be a usable M - roughly, and there are various O(1) factors here which you probably want to look up in Hardy & Wright, if D is the denominator of a continued fraction convergent then DR will be within about 1/D of an integer.

Code:
default(realprecision,500)
p=Pi()
M=contfracpnqn(contfrac(p,21)) 
M[2,1]*p
If you want a worst-case term, there's a nice theorem that phi = (1+sqrt(5))/2 is the hardest number to approximate with continued fractions, and the nth denominator of the continued fraction of phi is the nth Fibonacci number. So if you take your epsilon, and let n be the index of the first Fibonacci number larger than the reciprocal of epsilon, the denominator of the nth continued fraction convergent of R will definitely be a usable multiplier.
Really helpful - thank you - plenty for me to get my teeth into there!

Regards,

Mick.
mickfrancis is offline   Reply With Quote
Old 2017-02-27, 16:46   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

497110 Posts
Default

Given a real number r, and a small positive value e arbitrarily close to 0,

It depends, of course, on how you are given the real number. A numerical approximation to some prescribed number of decimal or binary digits, would be amenable to conversion to a "simple continued fraction" (an alternative search term). Also pursuant to fivemack's mention of the infinite SCF whose partial quotients are all 1, I mention Roth's Theorem which shows that algebraic numbers are "almost always" hard to approximate very well by rational numbers.

It is generally difficult to know both numerical and SCF representations of a given number. See, however, the following paper.

Last fiddled with by Dr Sardonicus on 2017-02-27 at 16:50
Dr Sardonicus is offline   Reply With Quote
Old 2017-02-27, 21:42   #7
mickfrancis
 
Apr 2014
Marlow, UK

23·7 Posts
Default Changing the question...

Having given some thought to this, I realise that what I really want is a way to find integer values for m such that
 <br />
(ceil(mr))^2- (mr)^2 < (mr)^s<br />
<br />


where s <= 1. I'm guessing this is a different kettle of fish...




Last fiddled with by mickfrancis on 2017-02-27 at 21:47
mickfrancis is offline   Reply With Quote
Old 2017-02-27, 21:58   #8
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7×307 Posts
Default

Quote:
Originally Posted by mickfrancis View Post
Given a real number r, and a small positive value e arbitrarily close to 0, does anyone know of a fast way to find integer multipliers m such that either:
{mr} < e
or
1 - {mr} < e
(where {mr} is the fractional part of mr)

Thanks in advance for any help,

Mick.
Can you please clarify with a numeric example.
if
r=0.5
and
e=0.25
How can there be an integer m where
m*0.5<0.25?
a1call is offline   Reply With Quote
Old 2017-02-27, 22:16   #9
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7×307 Posts
Default

If you are looking for an algebraic equivalence to ceil or floor function, then I can assure you that no such equivalence exists. I wasted years trying to find one, only to realize it is equivalent to a general and complete formula for primes. That means that if such an algebraic function could exist, then it could be used to reduce the series function consisting of floor()s to get a complete prime numbers formula (which would generate all prime numbers as function of n).

Last fiddled with by a1call on 2017-02-27 at 22:27
a1call is offline   Reply With Quote
Old 2017-02-27, 22:27   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3×1,657 Posts
Default

Quote:
Originally Posted by mickfrancis View Post
Having given some thought to this, I realise that what I really want is a way to find integer values for m such that
 <br />
(ceil(mr))^2- (mr)^2 < (mr)^s<br />
<br />


where s <= 1. I'm guessing this is a different kettle of fish...



This would appear to mean something like

| N/m - r| < c/m^(2 - s)

(c = positive constant), which is more easily achievable than having the exponent 2 in the denominator.

There is a notion of "best rational approximations," i.e. fractional approximations which are closer than any fraction with a smaller denominator. These consist of the "intermediate convergents" for the SCF. I know it's somewhere in Chrystal's Textbook of Algebra, but I'm sure something can be found on line.
Dr Sardonicus is offline   Reply With Quote
Old 2017-02-27, 23:34   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by mickfrancis View Post
Having given some thought to this, I realise that what I really want is a way to find integer values for m such that
 <br />
(ceil(mr))^2- (mr)^2 < (mr)^s<br />
<br />


where s <= 1. I'm guessing this is a different kettle of fish...



well the equivalent inequalities depend on a few things if m and r are the same sign then all values are positive ( because a negative times a negative is a positive) if they are different sign then mr is negative and with s<=1 it could be an inequality where you ask if a real value is less than an imaginary or complex number. so if we don't want to ask that question it may be safer to stay with the m values that are of the same sign as r. also if mr were negative then in theory you get -floor(abs(mr)) as an equivalent edit: to ceil

Last fiddled with by science_man_88 on 2017-02-27 at 23:46
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Using quarternions instead of Gaussian primes when factoring a real number? Stargate38 Factoring 4 2012-04-10 04:20
calculate logarithm base 2 of number very close 1 thehealer Other Mathematical Topics 9 2011-04-20 14:02
To create a real random number, shaxper Miscellaneous Math 58 2004-12-13 00:22
Largest number in the real universe danjmi Science & Technology 17 2004-09-26 20:25
Probability of finding a prime number Deamiter Software 4 2002-10-11 16:36

All times are UTC. The time now is 11:04.


Mon Oct 18 11:04:45 UTC 2021 up 87 days, 5:33, 0 users, load averages: 1.62, 1.57, 1.55

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