wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> A-sequences
        
(Message started by: Barukh on Jan 4^th, 2009, 10:38am)

Title: A-sequences
Post by Barukh on Jan 4^th, 2009, 10:38am

Let n be a positive integer. We call a sequence of positive numbers a₁ < a₂ < … < a_r http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif n an a-sequence for number n if for every prime number p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif n the set a₁ mod p, a₂ mod p, …, a_r 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) > http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif(n), the number of primes less than or equal to n.
4) Calculate r(1000000).

Title: Re: A-sequences
Post by TenaliRaman on Jan 4^th, 2009, 2:04pm

[hide]1] 116, 2] 451[/hide] ??

-- AI

Title: Re: A-sequences
Post by Barukh on Jan 4^th, 2009, 11:11pm

on 01/04/09 at 14:04:39, TenaliRaman wrote:

[hide]1] 116, 2] 451[/hide] ??

??? ???

Title: Re: A-sequences
Post by TenaliRaman on Jan 5^th, 2009, 1:31pm

on 01/04/09 at 23:11:36, 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.

[hide]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.[/hide]

Title: Re: A-sequences
Post by SMQ on Jan 5^th, 2009, 6:03pm

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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif(x) overall (unsurprisingly, considering question 3)...

--SMQ

Title: Re: A-sequences
Post by TenaliRaman on Jan 6^th, 2009, 2:32am

on 01/05/09 at 18:03:29, SMQ wrote:

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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif(n).

-- AI

Title: Re: A-sequences
Post by Eigenray on Jan 6^th, 2009, 7:37am

on 01/04/09 at 10:38:10, Barukh wrote:

3) Find the smallest number n for which r(n) > http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif(n), the number of primes less than or equal to n.

n=1 ::)

What are you getting for small values of n? Taking a_i 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif_p<n (1-1/p) ~ n/log n ~ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif(n).

Title: Re: A-sequences
Post by SMQ on Jan 6^th, 2009, 8:09am

on 01/06/09 at 07:37:55, Eigenray wrote:

What are you getting for small values of n?

r(n) =

n = 2
3 < n < 6
7 < n < 8
9 < n < 12
13 < n < 16
17 < n < 20
21 < n < 26
27 < n < 30
31 < n < 32
33 < n < 36
37 < n < 42
43 < n < 48
49 < n < 50
51 < n < 56
57 < n < 60
61 < n < 66
67 < n < 70
71 < n < 76
77 < n < 80
81 < n < 84
85 < n < 90
91 < n < 94
95 < n < 100
101 < n < 110
111 < n < 114
115 < n < 120
121 < n < 126
127 < n < 130
131 < n < 136
137 < n < 140
141 < n < 146
147 < n < 152

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

--SMQ

Title: Re: A-sequences
Post by towr on Jan 6^th, 2009, 8:37am

http://www.research.att.com/~njas/sequences/A023193

Title: Re: A-sequences
Post by SMQ on Jan 6^th, 2009, 10:45am

Well, then, based on this link (http://www.opertech.com/primes/k-tuples.html) (warning, spoilers!) we have:
1) [hide]r(1000) = 163[/hide]
2) [hide]r(4916) > 661[/hide]
3) [hide]2227 < n < 3159[/hide]
4) finding an exact value is well beyond the the current state-of-the-art, but [hide]likely "somewhat" less than[/hide] http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif(1000000) = 78498.

It appears that [hide]exhaustive search is still state-of-the-art (at least as of early November) for producing exact answers[/hide], so answering any of questions 2 through 4 [hide]exactly will advance the sum of human knowledge.[/hide] 8)

--SMQ

Title: Re: A-sequences
Post by TenaliRaman on Jan 6^th, 2009, 1:14pm

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

Title: Re: A-sequences
Post by SMQ on Jan 6^th, 2009, 4:48pm

on 01/06/09 at 13:14:49, 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 {a₁, a₂, ..., a_i} is an a-sequence for some n, then {a₁, a₂, ..., a_i-1} is an a-sequence for n-1, so r(n) never increases by more than 1.
- If {a₁, a₂, ..., a_i} is an a-sequence for some n, then {a₁+k, a₂+k, ..., a_i+k}: 1-a₁ < 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

Title: Re: A-sequences
Post by Barukh on Jan 7^th, 2009, 3:44am

Nice progress! BTW, I wasn't aware of the existence of spoiler link. :D

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?

Title: Re: A-sequences
Post by ktuple on Jan 10^th, 2009, 12:30am

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

Title: Re: A-sequences
Post by pex on Jan 10^th, 2009, 1:11am

on 01/07/09 at 03:44:32, 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.