A particularly peculiar problem

fivemack · 2008-10-15, 12:45

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

Zeta-Flux · 2008-10-15, 14:50

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 · 2008-10-15, 17:50

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?

davieddy · 2008-10-15, 23:58

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.

axn · 2008-10-16, 00:20

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 :-(

fivemack · 2008-10-16, 07:12

Quote:

Originally Posted by Zeta-Flux

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.

ATH · 2008-10-16, 16:00

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.

Bill Daly · 2008-11-14, 07:56

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.

2008-10-15, 12:45	#1
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²·131 Posts	A particularly peculiar problem Let A = 235711131719232931 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

2008-10-16, 00:20	#5
axn Jun 2003 5,051 Posts	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

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

2008-10-15, 14:50	#2
Zeta-Flux May 2003 7×13×17 Posts	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.

2008-10-15, 17:50	#3
Zeta-Flux May 2003 7·13·17 Posts	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?

2008-10-15, 23:58	#4
davieddy "Lucan" Dec 2006 England 194A₁₆ Posts	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.

2008-10-16, 16:00	#7
ATH Einyen Dec 2003 Denmark 3⁵·13 Posts	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.

2008-11-14, 07:56	#8
Bill Daly Oct 2008 5₁₆ Posts	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.