Author |
Topic: A-sequences (Read 2398 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
A-sequences
« on: Jan 4th, 2009, 10:38am » |
 Quote  Modify
|
Let n be a positive integer. We call a sequence of positive numbers a1 < a2 < … < ar  n an a-sequence for number n if for every prime number p n the set a1 mod p, a2 mod p, …, ar mod p contains less than p numbers.
(For example, a sequence 2, 4 is an a-sequence for n = 6, while sequence 1, 3, 5 is not).
Let r(n) be the size of the longest a-sequence for number n.
Problems:
1) Calculate r(1000).
2) Calculate r(4916).
3) Find the smallest number n for which r(n) >  (n), the number of primes less than or equal to n.
4) Calculate r(1000000).
|
|
 IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: A-sequences
« Reply #1 on: Jan 4th, 2009, 2:04pm » |
Quote Modify
|
1] 116, 2] 451 ??
-- AI
|
| « Last Edit: Jan 4th, 2009, 2:19pm by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: A-sequences
« Reply #3 on: Jan 5th, 2009, 1:31pm » |
Quote Modify
|
on Jan 4th, 2009, 11:11pm, Barukh wrote:
Ok! I was generally asking if the answers to (1) and (2) are right. However, given your reaction, I guess I was wrong.
Basically I wrote a program to find the longest sequence.
The algo was to basically consider the entire sequence to be a-sequence and start pruning with the primes from largest to smallest. The pruning was done as follows :
1] find the equivalence class [0], [1], .... [p-1].
2] Remove the class with the smallest size and consider the rest as the longest a-sequence. The final sequence will satisfy the necessary criterions to be an a-sequence. Though I am not entirely sure whether it is the longest sequence.
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A-sequences
« Reply #4 on: Jan 5th, 2009, 6:03pm » |
Quote Modify
|
When there are multiple smallest equivalence classes, it does matter which one you remove, and I haven't been able to find a pattern yet. However, the growth of r(x) looks to be fairly close to the growth of (x) overall (unsurprisingly, considering question 3)...
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: A-sequences
« Reply #5 on: Jan 6th, 2009, 2:32am » |
Quote Modify
|
on Jan 5th, 2009, 6:03pm, SMQ wrote:When there are multiple smallest equivalence classes, it does matter which one you remove, and I haven't been able to find a pattern yet. However, the growth of r(x) looks to be fairly close to the growth of (x) overall (unsurprisingly, considering question 3)...
--SMQ |
|
Ouch, you are right! I was missing a lot of cases apparently. Unfortunately, the modifications have slowed the computation down pretty heavily  . However, I am now able to see a similarity between r(n) and (n).
-- AI
|
| « Last Edit: Jan 6th, 2009, 2:33am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: A-sequences
« Reply #6 on: Jan 6th, 2009, 7:37am » |
Quote Modify
|
on Jan 4th, 2009, 10:38am, Barukh wrote:
3) Find the smallest number n for which r(n) > (n), the number of primes less than or equal to n.
|
|
n=1 
What are you getting for small values of n? Taking ai as small as possible gives
1, 3, 7, 9, 13, 19, 21, 27, 31, 33, ...,
which has 157 terms below n=1000.
Heuristically I'd imagine r(n) ~ n  p<n (1-1/p) ~ n/log n ~ (n).
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A-sequences
« Reply #9 on: Jan 6th, 2009, 10:45am » |
Quote Modify
|
Well, then, based on this link (warning, spoilers!) we have:
1) r(1000) = 163
2) r(4916) > 661
3) 2227 < n < 3159
4) finding an exact value is well beyond the the current state-of-the-art, but likely "somewhat" less than (1000000) = 78498.
It appears that exhaustive search is still state-of-the-art (at least as of early November) for producing exact answers, so answering any of questions 2 through 4 exactly will advance the sum of human knowledge. 
--SMQ
|
| « Last Edit: Jan 6th, 2009, 12:35pm by SMQ » |
IP Logged |
--SMQ
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: A-sequences
« Reply #10 on: Jan 6th, 2009, 1:14pm » |
Quote Modify
|
Not to digress but, there is one pattern that I have been trying to explain to myself.
The r(n)'s seem to increase by just 1 or 0 with increment in n and increment by 1 in r(n) happens at either n+2 or n+4 or n+6 (except n =1).
Not sure, if this pattern will sustain. If it does, then I wonder why?
-- AI
|
| « Last Edit: Jan 6th, 2009, 1:21pm by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A-sequences
« Reply #11 on: Jan 6th, 2009, 4:48pm » |
Quote Modify
|
on Jan 6th, 2009, 1:14pm, TenaliRaman wrote:| Not sure, if this pattern will sustain. If it does, then I wonder why? |
|
Well, there's an n+10 from 101 to 111, but in general:
- Any a-sequence for some n is also an a-sequence for all n+k, therefore r(n) is non-decreasing.
- If {a1, a2, ..., ai} is an a-sequence for some n, then {a1, a2, ..., ai-1} is an a-sequence for n-1, so r(n) never increases by more than 1.
- If {a1, a2, ..., ai} is an a-sequence for some n, then {a1+k, a2+k, ..., ai+k}: 1-a1 < k is an a-sequence for n+k.
- Since an a-sequence can contain either even or odd numbers, but not both, and since by the previous rule any a-sequence in even numbers is also an a-sequence (in odd numbers) if each term is reduced by 1, r(n) never increases for even n.
So r(n) always stays the same or increments by 1, and the increments always happen at odd n.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A-sequences
« Reply #12 on: Jan 7th, 2009, 3:44am » |
Quote Modify
|
Nice progress! BTW, I wasn't aware of the existence of spoiler link. 
Yes, the only way to obtain optimal a-sequences (which, as you probably already noticed, are called admissible) is exhastive search, which becomes impractical at around n = 2200.
Still, I beleive, there are quite interesting questions how to make calculations efficient! Let's try:
5) Can you provide an optimal a-sequence for n = 1000?
6) How close to the known r(4916) can you reach?
|
|
IP Logged |
|
|
|
ktuple
Newbie
Posts: 1
|
|
Re: A-sequences
« Reply #13 on: Jan 10th, 2009, 12:30am » |
Quote Modify
|
for those interested --
exhaustive search current limit is at
a width of 2279
also, super dense patterns have been
identified for widths up to 41741 that
are not max density, but pattern does
exist and is stored. Extremes given at
http://www.opertech.com/primes/trophycase.html
The density appears to be overtaking
pi(w) -- graph at at least a linear rate,
actually appears to be concave up which
would violate the H-L k-tuple conjecture.
http://www.opertech.com/primes/trophy.bmp
Almost 40 million superdense patterns
found. The number of known variations
for each width is currently about 1024.
Plot of variation counts at
http://www.opertech.com/primes/varcount.bmp
Also, have seen 4916 reference, the values about
2279 are just known densities, not maximums.
Curious as to interest in this, have been on the
problem for 17 years, and very little interest by
others in the past.
Tom
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: A-sequences
« Reply #14 on: Jan 10th, 2009, 1:11am » |
Quote Modify
|
on Jan 7th, 2009, 3:44am, Barukh wrote:| Can you provide an optimal a-sequence for n = 1000? |
|
1, 3, 7, 13, 19, 21, 31, 39, 43, 49, 57, 63, 69, 81, 87, 91, 97, 109, 111, 117, 123, 127, 133, 139, 141, 147, 153, 157, 159, 169, 171, 183, 189, 193, 199, 201, 211, 213, 217, 223, 229, 241, 243, 249, 271, 273, 277, 279, 283, 291, 301, 307, 309, 327, 339, 343, 349, 357, 361, 369, 379, 381, 391, 393, 397, 399, 403, 411, 417, 421, 423, 427, 439, 453, 459, 463, 477, 481, 483, 487, 489, 501, 507, 511, 529, 531, 547, 549, 553, 559, 567, 573, 577, 579, 591, 601, 603, 607, 609, 613, 619, 621, 631, 633, 643, 651, 657, 663, 669, 687, 697, 699, 703, 711, 717, 721, 729, 733, 739, 747, 757, 763, 769, 771, 777, 783, 787, 799, 801, 811, 813, 817, 823, 829, 837, 841, 853, 859, 861, 867, 871, 873, 879, 889, 897, 901, 907, 921, 927, 931, 937, 939, 943, 949, 951, 967, 969, 973, 981, 991, 993, 997, 999
seems to work.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print