 mersenneforum.org A particularly peculiar problem
 Register FAQ Search Today's Posts Mark Forums Read 2008-10-15, 12:45 #1 fivemack (loop (#_fork))   Feb 2006 Cambridge, England 2·29·109 Posts 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   2008-10-15, 14:50 #2 Zeta-Flux   May 2003 101111100102 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 2×761 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 6,451 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, 00:20 #5 axn   Jun 2003 4,721 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   2008-10-16, 07:12   #6
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

2·29·109 Posts 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.   2008-10-16, 16:00 #7 ATH Einyen   Dec 2003 Denmark 2,969 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.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post petrw1 PrimeNet 5 2011-01-14 18:01 Raman Puzzles 13 2010-02-13 05:25 spkarra Math 8 2009-07-20 22:47 jasong jasong 7 2009-01-01 00:50 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