mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2008-10-15, 12:45   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·29·109 Posts
Default A particularly peculiar problem

Let A = 2*3*5*7*11*13*17*19*23*29*31

Given: a number between 0 and A-1, coprime to A

Supply: its index 0..phi(A)-1 in the set of integers coprime to A listed in increasing order (or in any other order you choose)

Please don't use a 31GB lookup table

This might actually be useful for singleton removal in very large sets of relations for NFS, though I suspect it's only a moderate improvement (15.2% of numbers in 0..A-1 are coprime to A, whilst 26.7% of numbers in 0..29 are coprime to 30) over

=(mod(G15,5)-1)*2+(mod(G15,6)-1)/4

as the reduction from 0..29 to 0..7 for numbers coprime to 30
fivemack is offline   Reply With Quote
Old 2008-10-15, 14:50   #2
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

101111100102 Posts
Default

What is the definition of "index" you are using? From your use of \phi(A), I imagine you mean something related to the order modulo A.
Zeta-Flux is offline   Reply With Quote
Old 2008-10-15, 17:50   #3
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

2×761 Posts
Default

Oh, I think I understand what you meant now. Are you saying, "Take the first \phi(A) integers which are coprime to A, in increasing order, and subscript them according to their relationship in the set. Give a simple algorithm for picking the index where an integer occurs in this set."? That seems like an odd request. Especially since you don't care about the order. What information do you really want to get your hands on?
Zeta-Flux is offline   Reply With Quote
Old 2008-10-15, 23:58   #4
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

6,451 Posts
Default

Hope this is relevant:
When I first programmed a Sieve of Eratosthanes
(at the age of 50 something) I compressed 30 integers
into 8 by excluding multiples of 2,3 and 5.
Further compression runs into a Law of Diminishing Returns
rather rapidly.
davieddy is offline   Reply With Quote
Old 2008-10-16, 00:20   #5
axn
 
axn's Avatar
 
Jun 2003

4,721 Posts
Default

Since this is the puzzle forum and all...
We use variable base encoding to achieve this. Let N be the number for which we need to find the index.

Compute w(b) = (N mod b)-1, for b = 3,5,7,...,31 (no need to bother with 2)
Then Index(N) = ((w(3) * (5-1) + w(5)) * (7-1) + w(7)) * (11-1) + w(11) ...
This will give you the index.

To find N given then index, you need to do the mods to obtain the w() values and then do CRT to get back N.

This is NOT in any specific sort order :-(

Last fiddled with by axn on 2008-10-16 at 00:22
axn is online now   Reply With Quote
Old 2008-10-16, 07:12   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·29·109 Posts
Default

Quote:
Originally Posted by Zeta-Flux View Post
Oh, I think I understand what you meant now. Are you saying, "Take the first \phi(A) integers which are coprime to A, in increasing order, and subscript them according to their relationship in the set. Give a simple algorithm for picking the index where an integer occurs in this set."? That seems like an odd request. Especially since you don't care about the order. What information do you really want to get your hands on?
I want to pack primes into a bit array as efficiently as possible for singleton removal. Davieddy is probably right that avoiding the blanks at multiples of 3 and 5 is likely to be good enough; getting to something a bit bigger with phi(A)/A < 1/4 would allow easy singleton removal up to 2^36 on an 8-gigabyte machine (you need two bits per prime per side) but 480/2310 is small enough to work and 2310 is small enough that lookup table is the right answer.

Actually you need one three-state counter per prime per side, and the 5-trits-in-a-byte trick (since 3^5 is just less than 2^8) would also let you work up to 2^36 using only A=30.
fivemack is offline   Reply With Quote
Old 2008-10-16, 16:00   #7
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2,969 Posts
Default

This might be what you are looking for?

http://www.rsok.com/~jrm/printprimes.html

I used the 48bits / 210 integers scheme to pack down all prime numbers up to 10^10 (actually up to 10,000,000,080) in a file taking 285,714,288 bytes.
ATH is online now   Reply With Quote
Old 2008-11-14, 07:56   #8
Bill Daly
 
Oct 2008

5 Posts
Default

It can be done, but it might be slowish. A is the product of 11 primes, which we can number as p1..p11 for convenience. Suppose that n is the number in question. The number of numbers less than n which are divisible by p_i is floor(n/p_i). Similarly, the number of numbers less than n which are divisible by both p_i and p_j is floor(n/(p_i*p_j)). Etc. Suppose that we write K(n,m) for the number of numbers less than n which are divisible by a subset of exactly m primes among p1..p11. This means computing K(n,1)..K(n,10) (assuming that n is less than A). By the rule of inclusion/exclusion, the number of numbers less than n which are divisible by at least one of the primes p1..p11 will be K(n,1)-K(n,2)+K(n,3)-K(n,4)+...-K(n,10). The index of n will then be this number subtracted from n, i.e. the number of numbers less than n which are coprime to A.

As to computational speed. The calculation of K(n,1) involves the sum of 11 numbers of the form floor(n/p_i). Similarly the calculation of K(n,2) involves the sum of 55 numbers of the form floor(n/d), where d is the product of exactly 2 of the p_i. Etc. In general, the calculation of K(n,m) will require the calculation of the sum of C(11,m) numbers of the form floor(n/d), where d is the product of exactly m of the p_i. The total number of summands will be 2^11-2, which is tolerable. (C(11,m) is a binomial coefficient.)

I don't offhand see a simpler approach. There may be a few shortcuts along the way.

For the record A = 200560490130, and phi(A) = 30656102400, both of which are too large for 32-bit arithmetic. They both fit into doubles, though.
Bill Daly is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Peculiar activity in the 1M range... petrw1 PrimeNet 5 2011-01-14 18:01
Sum of two squares: Peculiar property Raman Puzzles 13 2010-02-13 05:25
Peculiar behaviour of prime numbers ..... spkarra Math 8 2009-07-20 22:47
Peculiar Case of Benjamin Button is AWESOME!!!!!!! jasong jasong 7 2009-01-01 00:50
51 problem Neves Puzzles 15 2004-02-05 23:11

All times are UTC. The time now is 05:00.

Sat Oct 31 05:00:08 UTC 2020 up 51 days, 2:11, 2 users, load averages: 1.98, 1.65, 1.73

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