Multiplicative sequences: Difference between revisions

From Polymath Wiki
Jump to navigationJump to search
Alec (talk | contribs)
169 edits
Longest completely multiplicative sequence.
 
Thomas (talk | contribs)
59 edits
No edit summary
 
(25 intermediate revisions by 4 users not shown)
Line 1: Line 1:
Any completely-multiplicative sequence of length <math>247</math> has discrepancy more than <math>2</math>. There are 500 sequences of length <math>246</math> with discrepancy <math>2</math>. Here is one example:
==Case C=2==
 
Any completely-multiplicative sequence of length <math>247</math> has discrepancy more than <math>2</math>.  
 
===Data and plots===
 
There are 500 sequences of length <math>246</math> with discrepancy <math>2</math>, all of which agree at primes up to and including <math>67</math>. Here is one example:


  0 + - - + - + - - + + + - - + + + - -
  0 + - - + - + - - + + + - - + + + - -
Line 14: Line 20:
  + + - + + - + + - - - - + - + + + + -
  + + - + + - + + - - - - + - + + + + -
  - - - + - + + + + - - - + + - - + - -
  - - - + - + + + + - - - + + - - + - -
Here are the values this sequence takes at the first few primes. The primes up to 101 that go to -1 are 2, 3, 5, 7, 13, 17, 23, 37, 41, 43, 47, 67, 71, 83, 89, 97, 101. The primes less than 100 that go to 1 are 11, 19, 29, 31, 53, 59, 61, 73, 79.
The total number of such multiplicative sequences for each length can be generated with Alec's python script.
Here is a [http://thomas1111.files.wordpress.com/2010/01/multnumzoom.png plot of this data], and [http://www.obtext.com/erdos/log_number_of_cm_seqs.png a plot of the log of the data], and here are the precise numbers:
length  number
2 2
3 3
4 3
5 4
6 4
7 7
8 7
9 6
10 6
11 10
12 10
13 15
14 15
15 14
16 14
17 21
18 21
19 34
20 34
21 24
22 24
23 38
24 38
25 28
26 28
27 23
28 23
29 34
30 34
31 54
32 54
33 37
34 37
35 28
36 28
37 40
38 40
39 31
40 31
41 48
42 48
43 72
44 72
45 57
46 57
47 89
48 89
49 81
50 81
51 62
52 62
53 92
54 92
55 55
56 55
57 44
58 44
59 68
60 68
61 111
62 111
63 83
64 83
65 71
66 71
67 113
68 113
69 97
70 97
71 157
72 157
73 240
74 240
75 175
76 175
77 125
78 125
79 185
80 185
81 178
82 178
83 286
84 286
85 212
86 212
87 178
88 178
89 276
90 276
91 163
92 163
93 138
94 138
95 119
96 119
97 176
98 176
99 129
100 129
101 198
102 198
103 315
104 315
105 277
106 277
107 426
108 426
109 656
110 656
111 485
112 485
113 846
114 846
115 502
116 502
117 256
118 256
119 198
120 198
121 112
122 112
123 82
124 82
125 82
126 82
127 100
128 100
129 84
130 84
131 134
132 134
133 56
134 56
135 44
136 44
137 61
138 61
139 105
140 105
141 84
142 84
143 72
144 72
145 55
146 55
147 48
148 48
149 72
150 72
151 120
152 120
153 72
154 72
155 72
156 72
157 132
158 132
159 112
160 112
161 112
162 112
163 184
164 184
165 164
166 164
167 246
168 246
169 234
170 234
171 168
172 168
173 246
174 246
175 246
176 246
177 246
178 246
179 408
180 408
181 624
182 624
183 414
184 414
185 384
186 384
187 286
188 286
189 286
190 286
191 304
192 304
193 392
194 392
195 362
196 362
197 468
198 468
199 812
200 812
201 776
202 776
203 626
204 626
205 386
206 386
207 386
208 386
209 386
210 386
211 694
212 694
213 573
214 573
215 471
216 471
217 279
218 279
219 259
220 259
221 259
222 259
223 354
224 354
225 125
226 125
227 125
228 125
229 250
230 250
231 250
232 250
233 375
234 375
235 250
236 250
237 250
238 250
239 500
240 500
241 750
242 750
243 500
244 500
245 500
246 500<math>Insert formula here</math>
247 0
And the same data in Mathematica format: {{1,1},{2,2},{3,3},{4,3},{5,4},{6,4},{7,7},{8,7},{9,6},{10,6},{11,10},{12,10},{13,15},{14,15},{15,14},{16,14},{17,21},{18,21},{19,34},{20,34},{21,24},{22,24},{23,38},{24,38},{25,28},{26,28},{27,23},{28,23},{29,34},{30,34},{31,54},{32,54},{33,37},{34,37},{35,28},{36,28},{37,40},{38,40},{39,31},{40,31},{41,48},{42,48},{43,72},{44,72},{45,57},{46,57},{47,89},{48,89},{49,81},{50,81},{51,62},{52,62},{53,92},{54,92},{55,55},{56,55},{57,44},{58,44},{59,68},{60,68},{61,111},{62,111},{63,83},{64,83},{65,71},{66,71},{67,113},{68,113},{69,97},{70,97},{71,157},{72,157},{73,240},{74,240},{75,175},{76,175},{77,125},{78,125},{79,185},{80,185},{81,178},{82,178},{83,286},{84,286},{85,212},{86,212},{87,178},{88,178},{89,276},{90,276},{91,163},{92,163},{93,138},{94,138},{95,119},{96,119},{97,176},{98,176},{99,129},{100,129},{101,198},{102,198},{103,315},{104,315},{105,277},{106,277},{107,426},{108,426},{109,656},{110,656},{111,485},{112,485},{113,846},{114,846},{115,502},{116,502},{117,256},{118,256},{119,198},{120,198},{121,112},{122,112},{123,82},{124,82},{125,82},{126,82},{127,100},{128,100},{129,84},{130,84},{131,134},{132,134},{133,56},{134,56},{135,44},{136,44},{137,61},{138,61},{139,105},{140,105},{141,84},{142,84},{143,72},{144,72},{145,55},{146,55},{147,48},{148,48},{149,72},{150,72},{151,120},{152,120},{153,72},{154,72},{155,72},{156,72},{157,132},{158,132},{159,112},{160,112},{161,112},{162,112},{163,184},{164,184},{165,164},{166,164},{167,246},{168,246},{169,234},{170,234},{171,168},{172,168},{173,246},{174,246},{175,246},{176,246},{177,246},{178,246},{179,408},{180,408},{181,624},{182,624},{183,414},{184,414},{185,384},{186,384},{187,286},{188,286},{189,286},{190,286},{191,304},{192,304},{193,392},{194,392},{195,362},{196,362},{197,468},{198,468},{199,812},{200,812},{201,776},{202,776},{203,626},{204,626},{205,386},{206,386},{207,386},{208,386},{209,386},{210,386},{211,694},{212,694},{213,573},{214,573},{215,471},{216,471},{217,279},{218,279},{219,259},{220,259},{221,259},{222,259},{223,354},{224,354},{225,125},{226,125},{227,125},{228,125},{229,250},{230,250},{231,250},{232,250},{233,375},{234,375},{235,250},{236,250},{237,250},{238,250},{239,500},{240,500},{241,750},{242,750},{243,500},{244,500},{245,500},{246,500},{247,0}}
==Case C=3==
The maximum length for <math>C=3</math> is at least <math>13186</math>.
An example of that length is detailed [[Discrepancy 3 multiplicative sequence of length 13186|on this page]].
Length 1530:
+--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+-+--++
+--+++--+-+--+-+--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-
+--+-+--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+-
+--+++--+++--+-++-+-+--+-+--+++--+++--+-+--+++--+-+--+++--++
+--+-+--++---+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-
+--+-+--+++--+++--+-+--+-+--+-+--+++--+++--+-+--+++--+-+--++
+--+++--+-+--+++--+-+--+++--+++----+--+++--+-+--+++--+++--+-
+--+-+--+-+--+++--+++--+-+--+-+--+-++-+++--+++--+-+--+++--+-
+--+++--+++--+-+--+-++-+-+---++--+++--+-+--+++--+-+--+++--++
+--+-+--+-+--+-+--+++--+++--+-+--+-+--+-+--+++--++--++-+--++
+--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+++--+-+--++
---+++--+-+--+-+--+-+-++++--+++--+-+--+-+--+-+--+++--+++--+-
+--+++--+-+--+++--+++--+-+--+-+-++-+--++---+++----+--+++--+-
+--+++-++++--+-+--+-+--+-+--+++--+++--+-+--+-+--+-+--+++--++
+--+-+--+++--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--++
+--+-+--+++---++--+-+--+-+--+-+--+++--+++--+-+--+-+-++-+--++
+--+++--+-+--+++--+-+--+-+--+++--+-++-+++----+--+++--+++-++-
---+++--+-+--+++--+++--+-+--+-+--+-+--+++--+++--+-+--+-+--+-
+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+-+--+++--++
+--+-+--+++--+-+--+++--+++--+-+--+-+--+-++-++---+++-++-+--+-
+--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+++---+
+--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+-+--+++--+++--+-
++-+-+--+-+--+++--+++--+-+--+++--+-+--+++--++-+-+---++-+----
+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+-+--+++--++
+--+-+--+-+-++-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--++
+--+----++---+++--+-++-++++-+-
These are the primes sent to -1 in this example: 2, 3, 5, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97, 103, 107, 113, 127, 137, 157, 163, 167, 173, 193, 223, 227, 233, 251, 257, 263, 277, 283, 293, 307, 313, 317, 337, 347, 353, 367, 373, 383, 397, 433, 443, 463, 467, 487, 503, 509, 523, 547, 557, 563, 577, 587, 607, 613, 617, 643, 647, 653, 661, 673, 677, 727, 733, 743, 757, 761, 769, 773, 787, 797, 823, 827, 853, 857, 863, 877, 883, 887, 907, 937, 947, 967, 977, 983, 1013, 1021, 1033, 1063, 1087, 1093, 1097, 1103, 1117, 1123, 1153, 1163, 1187, 1213, 1217, 1223, 1237, 1259, 1277, 1283, 1297, 1303, 1307, 1327, 1423, 1427, 1433, 1447, 1483, 1487, 1493, 1511, 1523
This came from a search initialized by sending primes congruent to 2 or 3 mod 5, and the prime 5, to -1, and others to +1.
Length 852:
+--+++--+-+--+-+--+++--+++--+++--+-+--+-+--+++--+-+--+++--+-
+--+-+--+++--+-+--+++--+-+--+-+--+++--+++--+++--+-+--+-+--++
+--+++--+++--+-+--+-+--+++--++---+++--+-+--+-+--+++--+-+--++
+--+-+--+-+--++++-+-+--+++--+-+--+-+--+++--+++--+++--+-+--+-
+--+++--+-+--+++--+-+--+-+--+++--+++--++---+-+--+-+--+++--+-
++-+++--+-+--+-+--+++--+-+--+++--+-+--+-+--+++--+++--+++--+-
+--+-+--+++--+-+--+++-++-+--+-+---++--+++--+++--+-+--+-+--++
+--+-+--+++--+-+--+-+--+++--+-+-++++--+-+--+-+--+++--+++--++
+--+-+--+-+--+++---++--+++--+-+--+-+--+++--+++--+++--+-+--+-
+--+++--+-+--+++--+-++-+-+--+++--+-+--+++--+-+--+----+++--++
+---++--+-+--+-++-+++--+++--+++--+-+--+----+++--+++--+++--+-
+--+-+--+++--+-+--+++-++-+--+-+--+++--+-+--+++--+-+--+-+--++
+--+++--+++--+-+--+-+--+++--+++--+-++-+-+--+-----++--+++--++
+--+-+-++-+--+++--+-+--+++--+-+--+-+--+++--+-+--+++--+-+--+-
+-++++--+++-
These are the primes sent to -1 in this example: 2, 3, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97, 103, 107, 113, 127, 137, 151, 157, 163, 167, 173, 193, 223, 227, 233, 257, 263, 277, 281, 283, 293, 307, 313, 317, 337, 347, 353, 367, 373, 397, 433, 443, 457, 463, 467, 487, 499, 503, 523, 547, 557, 563, 577, 587, 593, 607, 613, 641, 643, 647, 653, 673, 677, 727, 733, 743, 769, 773, 787, 797, 823, 827.
This came from a search initialized by sending primes congruent to 2 or 3 mod 5 to -1 and others to +1.
Note that the only primes not congruent to 2 or 3 that are sent to -1 are 151, 281, 499, 641 and 769. [Are there some that are congruent to 2 or 3 that are sent to 1? If so, which are they?]
Length 819:
+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-+
+-++--+-++-----+-++-++--+-+++++--+-++--+--+-++--+--+-++-++--
+-++-----+-++-++--+-++-+++-+-+---+--+-++--+--+-++-+++-+-+-+-
+--+-++--++-+-++-+---+-++--+--+-++-++-++-+--+++---++--+--+-+
+--+--+-++-+++-+-++--+--+--++----+-++-+++-+-++--+----++-++--
++++-++--+-++--+--+-++-++--+-+--++--+-++--+---+++--+--+++--+
+--+++---+--+-++-+--+-+++-++--+-++---+-+-++--+--+-++-++--+++
---+--+-+++-+--+--+-+++--+++--+-+--+-++++---++-++--+-++--+--
+-++-+---+-++-++--+-+++-+---++---+--+--++++--+-++--+-++----+
++-+-++-++--+-++--+----++-++--+--+-++--+-+++-+--+-++--+-++-+
+-+---+-++--+--+++--+++-+-++-+---++++--++---++--+--+-++--++-
-+++--+-++-+---+--+--++++-++-+-+----+-+++++--+-+--+---+++++-
+--+-++-+----+++-++--+-++--+--+-+++--+-+--+++---+-++--+--+-+
+-++----++-+++---++-+++-+--+-+--++-++-+
The primes that go to -1 in this example are:
2, 3, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 73, 83, 101, 107, 113, 127, 131, 137, 149, 151, 167, 197, 199, 223, 229, 233, 239, 251, 257, 263, 271, 293, 311, 317, 331, 353, 359, 367, 379, 389, 397, 401, 421, 449, 457, 463, 467, 479, 487, 491, 557, 563, 569, 587, 593, 599, 619, 631, 643, 647, 653, 661, 673, 677, 691, 709, 733, 743, 757, 761, 773, 787, 797, 809, 811
Length 627:
+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-+
+-++--+-++-----+-++-++--+-+++++--+-++--+--+-++--+--+-++-++--
+-++-----+-++-++--+-++-+++-+-+---+--+-++--+--+-++-+++-+-+-+-
+--+-++--++-+-++-+---+-++--+--+-++-++-++-+--+++---++--+--+-+
+--+--+-++-+++-+-++--+--+--++----+-++-+++-+-++--+----++-++--
++++-++--+-+---+--+-++-++--+-++-++--+-++--+---+++--+--+++--+
+--+++---+--+-++-+--+-+++-++--+-++---+-+-++--+--+-++-++--+++
---+--+-+++-+--+--+-+++--+++--+-+--+-++++---++-++--+-++--+--
+-++-+---+-++-++--+-+++-+---++---+--+--++++--+-++--+-++----+
++-+-++-++--+-++--+----++-++--+--+-++--+-+++-+--+-++--+-++-+
+-+---+-++--+--+++--+++-+++
A sequence of length 545 that agrees with the maximal discrepancy-2 sequences at primes up to and including 67:
+--+-+--+++--+++--+-+--+++--+-+--+++--++---+-+--+-+-++-+--++
+--+++--+-+--+-+--+-++-+++---++--+-++-++--++--+--++--+++--+-
+-++-+--+-+--+++---++--+-+--+++--+-++--++-+-++--+-+-++-+-+--
+--+++--++--+--++---++-++---++-+--++-++-+--+++--+-+--+++--++
+--+----+++--+-+--+++--+-++-+----+++-++----++++-++--++-+--+-
+-++-++--++---++-++----+--+++-+--+++--+++--+--+-+++--+---+-+
+--++++-----++++--+-++-++--+-++----+-++++----+--+-++-++++-+-
-+---+-++-+-+++----++--+++--+----+-++-+++--++++-+----++++-+-
+--+-++--+-+-+-+--+-+--+++--+++--+-+----+--+++--+++-+--++-++
-+-++
This sequence is -1 at the following primes:
2, 3, 5, 7, 13, 17, 23, 37, 41, 43, 47, 67, 73, 83, 89, 101, 109, 113, 127, 137, 139, 167, 179, 191, 199, 211, 223, 227, 233, 257, 263, 271, 277, 281, 283, 313, 317, 337, 353, 359, 383, 389, 397, 421, 439, 443, 463, 491, 503, 523, 541
==General Case==
Here is some data on how the discrepancy of completely-multiplicative sequences grows as a function of length, depending on how missing values at prime indices are chosen.
Without loss of generality, one may always set <math>x_1=+1</math>
===Uniform choice===
Here is some data when the values of <math>x_n</math> are: a given +/-1 sequence when <math>n>1</math> is one of the first <math>N</math> primes, only the value <math>-1</math> for <math>n</math> any other prime, and a multiplicatively computed value when <math>n</math> is composite.
* N=1
** <math>x_1=+1</math>, <math>x_2=+1</math>: D(100)=21, D(1000)=107, D(10000)=407
** ...
* N=2
** <math>x_1=+1</math>, <math>x_2=+1</math>, <math>x_3=+1</math>: D(100)=34, D(1000)=262, D(10000)=1190
** ...
* N=3
** <math>x_1=+1</math>, <math>x_2=+1</math>, <math>x_3=+1</math>, <math>x_5=+1</math>: D(100)=25, D(1000)=413, D(10000)=2332
** ...
===Minimizing the discrepancy D up to the next prime===
[http://thomas1111.files.wordpress.com/2010/01/gensum_3000_sh0_disc.png Here is a plot] of D(n), the discrepancy as a function of length, as well as the partial sums of the first few HAP when one starts with <math>x_1=1</math> and ask that the value at prime <math>p</math> be either +1 or -1 depending on which allows to minimize <math>D(q)</math>, where <math>q</math> is the next prime.
[http://thomas1111.files.wordpress.com/2010/01/gensum_5000_s1124a_disc.png Here is a plot] doing the same thing but instead starting with [[The first 1124-sequence|the first 1124 sequence]] as a seed.
The two plots show that the partial sums do grow at least logarithmically.
===Minimizing the sum of partial HAP sums===
A method to choose a value at an undertermined prime <math>p</math> is to choose to impose <math>x_p=+1</math> or <math>x_p=-1</math> depending on which gave the smallest quantity <math>\ell_s(q)</math>, where <math>q</math> is the next prime and <math>\ell_s(q):=\sum_{d=1}^q s_d(q)</math> with <math>s_d(q)</math> itself the partial sum of the d-HAP up to <math>q</math>.
Here is [http://thomas1111.files.wordpress.com/2010/01/gensum_3000_sh0_plain.png a plot] obtained when setting only <math>x_1=+1</math>. On it is shown the function <math>f(x):=\log (x)</math> (the very flat curve), the partial sums of the sequence and its first few HAPs, and both <math>D(n)</math> and <math>-D(n)</math>.

Latest revision as of 19:44, 5 February 2010

Case C=2

Any completely-multiplicative sequence of length [math]\displaystyle{ 247 }[/math] has discrepancy more than [math]\displaystyle{ 2 }[/math].

Data and plots

There are 500 sequences of length [math]\displaystyle{ 246 }[/math] with discrepancy [math]\displaystyle{ 2 }[/math], all of which agree at primes up to and including [math]\displaystyle{ 67 }[/math]. Here is one example: 

0 + - - + - + - - + + + - - + + + - -
+ - + - - + + + - - + - + - - + + + -
- + + - - - + - + - - + - + - + + - +
- - + + + - - + + + - - + - - - + + -
+ - - + - + + - + + + - - - + + - - +
- + - - + + - - + + - - + - + + + - -
+ + + - - + - + - + + - + - - + - + -
- + + + - - - + + + - + - - - - + + +
- - + - + + - - + + - - - + + - - + -
+ - + + - + - + + - + - - + + + - - +
+ - - - + - + - - + - + + - + + - - -
+ + - + + - + + - - - - + - + + + + -
- - - + - + + + + - - - + + - - + - -


Here are the values this sequence takes at the first few primes. The primes up to 101 that go to -1 are 2, 3, 5, 7, 13, 17, 23, 37, 41, 43, 47, 67, 71, 83, 89, 97, 101. The primes less than 100 that go to 1 are 11, 19, 29, 31, 53, 59, 61, 73, 79.

The total number of such multiplicative sequences for each length can be generated with Alec's python script.

Here is a plot of this data, and a plot of the log of the data, and here are the precise numbers:

length number

2 2

3 3

4 3

5 4

6 4

7 7

8 7

9 6

10 6

11 10

12 10

13 15

14 15

15 14

16 14

17 21

18 21

19 34

20 34

21 24

22 24

23 38

24 38

25 28

26 28

27 23

28 23

29 34

30 34

31 54

32 54

33 37

34 37

35 28

36 28

37 40

38 40

39 31

40 31

41 48

42 48

43 72

44 72

45 57

46 57

47 89

48 89

49 81

50 81

51 62

52 62

53 92

54 92

55 55

56 55

57 44

58 44

59 68

60 68

61 111

62 111

63 83

64 83

65 71

66 71

67 113

68 113

69 97

70 97

71 157

72 157

73 240

74 240

75 175

76 175

77 125

78 125

79 185

80 185

81 178

82 178

83 286

84 286

85 212

86 212

87 178

88 178

89 276

90 276

91 163

92 163

93 138

94 138

95 119

96 119

97 176

98 176

99 129

100 129

101 198

102 198

103 315

104 315

105 277

106 277

107 426

108 426

109 656

110 656

111 485

112 485

113 846

114 846

115 502

116 502

117 256

118 256

119 198

120 198

121 112

122 112

123 82

124 82

125 82

126 82

127 100

128 100

129 84

130 84

131 134

132 134

133 56

134 56

135 44

136 44

137 61

138 61

139 105

140 105

141 84

142 84

143 72

144 72

145 55

146 55

147 48

148 48

149 72

150 72

151 120

152 120

153 72

154 72

155 72

156 72

157 132

158 132

159 112

160 112

161 112

162 112

163 184

164 184

165 164

166 164

167 246

168 246

169 234

170 234

171 168

172 168

173 246

174 246

175 246

176 246

177 246

178 246

179 408

180 408

181 624

182 624

183 414

184 414

185 384

186 384

187 286

188 286

189 286

190 286

191 304

192 304

193 392

194 392

195 362

196 362

197 468

198 468

199 812

200 812

201 776

202 776

203 626

204 626

205 386

206 386

207 386

208 386

209 386

210 386

211 694

212 694

213 573

214 573

215 471

216 471

217 279

218 279

219 259

220 259

221 259

222 259

223 354

224 354

225 125

226 125

227 125

228 125

229 250

230 250

231 250

232 250

233 375

234 375

235 250

236 250

237 250

238 250

239 500

240 500

241 750

242 750

243 500

244 500

245 500

246 500[math]\displaystyle{ Insert formula here }[/math]

247 0

And the same data in Mathematica format: {{1,1},{2,2},{3,3},{4,3},{5,4},{6,4},{7,7},{8,7},{9,6},{10,6},{11,10},{12,10},{13,15},{14,15},{15,14},{16,14},{17,21},{18,21},{19,34},{20,34},{21,24},{22,24},{23,38},{24,38},{25,28},{26,28},{27,23},{28,23},{29,34},{30,34},{31,54},{32,54},{33,37},{34,37},{35,28},{36,28},{37,40},{38,40},{39,31},{40,31},{41,48},{42,48},{43,72},{44,72},{45,57},{46,57},{47,89},{48,89},{49,81},{50,81},{51,62},{52,62},{53,92},{54,92},{55,55},{56,55},{57,44},{58,44},{59,68},{60,68},{61,111},{62,111},{63,83},{64,83},{65,71},{66,71},{67,113},{68,113},{69,97},{70,97},{71,157},{72,157},{73,240},{74,240},{75,175},{76,175},{77,125},{78,125},{79,185},{80,185},{81,178},{82,178},{83,286},{84,286},{85,212},{86,212},{87,178},{88,178},{89,276},{90,276},{91,163},{92,163},{93,138},{94,138},{95,119},{96,119},{97,176},{98,176},{99,129},{100,129},{101,198},{102,198},{103,315},{104,315},{105,277},{106,277},{107,426},{108,426},{109,656},{110,656},{111,485},{112,485},{113,846},{114,846},{115,502},{116,502},{117,256},{118,256},{119,198},{120,198},{121,112},{122,112},{123,82},{124,82},{125,82},{126,82},{127,100},{128,100},{129,84},{130,84},{131,134},{132,134},{133,56},{134,56},{135,44},{136,44},{137,61},{138,61},{139,105},{140,105},{141,84},{142,84},{143,72},{144,72},{145,55},{146,55},{147,48},{148,48},{149,72},{150,72},{151,120},{152,120},{153,72},{154,72},{155,72},{156,72},{157,132},{158,132},{159,112},{160,112},{161,112},{162,112},{163,184},{164,184},{165,164},{166,164},{167,246},{168,246},{169,234},{170,234},{171,168},{172,168},{173,246},{174,246},{175,246},{176,246},{177,246},{178,246},{179,408},{180,408},{181,624},{182,624},{183,414},{184,414},{185,384},{186,384},{187,286},{188,286},{189,286},{190,286},{191,304},{192,304},{193,392},{194,392},{195,362},{196,362},{197,468},{198,468},{199,812},{200,812},{201,776},{202,776},{203,626},{204,626},{205,386},{206,386},{207,386},{208,386},{209,386},{210,386},{211,694},{212,694},{213,573},{214,573},{215,471},{216,471},{217,279},{218,279},{219,259},{220,259},{221,259},{222,259},{223,354},{224,354},{225,125},{226,125},{227,125},{228,125},{229,250},{230,250},{231,250},{232,250},{233,375},{234,375},{235,250},{236,250},{237,250},{238,250},{239,500},{240,500},{241,750},{242,750},{243,500},{244,500},{245,500},{246,500},{247,0}}

Case C=3

The maximum length for [math]\displaystyle{ C=3 }[/math] is at least [math]\displaystyle{ 13186 }[/math].

An example of that length is detailed on this page.



Length 1530: 

+--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+-+--++
+--+++--+-+--+-+--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-
+--+-+--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+-
+--+++--+++--+-++-+-+--+-+--+++--+++--+-+--+++--+-+--+++--++
+--+-+--++---+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-
+--+-+--+++--+++--+-+--+-+--+-+--+++--+++--+-+--+++--+-+--++
+--+++--+-+--+++--+-+--+++--+++----+--+++--+-+--+++--+++--+-
+--+-+--+-+--+++--+++--+-+--+-+--+-++-+++--+++--+-+--+++--+-
+--+++--+++--+-+--+-++-+-+---++--+++--+-+--+++--+-+--+++--++
+--+-+--+-+--+-+--+++--+++--+-+--+-+--+-+--+++--++--++-+--++
+--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+++--+-+--++
---+++--+-+--+-+--+-+-++++--+++--+-+--+-+--+-+--+++--+++--+-
+--+++--+-+--+++--+++--+-+--+-+-++-+--++---+++----+--+++--+-
+--+++-++++--+-+--+-+--+-+--+++--+++--+-+--+-+--+-+--+++--++
+--+-+--+++--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--++
+--+-+--+++---++--+-+--+-+--+-+--+++--+++--+-+--+-+-++-+--++
+--+++--+-+--+++--+-+--+-+--+++--+-++-+++----+--+++--+++-++-
---+++--+-+--+++--+++--+-+--+-+--+-+--+++--+++--+-+--+-+--+-
+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+-+--+++--++
+--+-+--+++--+-+--+++--+++--+-+--+-+--+-++-++---+++-++-+--+-
+--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+++---+
+--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+-+--+++--+++--+-
++-+-+--+-+--+++--+++--+-+--+++--+-+--+++--++-+-+---++-+----
+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+-+--+++--++
+--+-+--+-+-++-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--++
+--+----++---+++--+-++-++++-+-

These are the primes sent to -1 in this example: 2, 3, 5, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97, 103, 107, 113, 127, 137, 157, 163, 167, 173, 193, 223, 227, 233, 251, 257, 263, 277, 283, 293, 307, 313, 317, 337, 347, 353, 367, 373, 383, 397, 433, 443, 463, 467, 487, 503, 509, 523, 547, 557, 563, 577, 587, 607, 613, 617, 643, 647, 653, 661, 673, 677, 727, 733, 743, 757, 761, 769, 773, 787, 797, 823, 827, 853, 857, 863, 877, 883, 887, 907, 937, 947, 967, 977, 983, 1013, 1021, 1033, 1063, 1087, 1093, 1097, 1103, 1117, 1123, 1153, 1163, 1187, 1213, 1217, 1223, 1237, 1259, 1277, 1283, 1297, 1303, 1307, 1327, 1423, 1427, 1433, 1447, 1483, 1487, 1493, 1511, 1523

This came from a search initialized by sending primes congruent to 2 or 3 mod 5, and the prime 5, to -1, and others to +1.

Length 852: 

+--+++--+-+--+-+--+++--+++--+++--+-+--+-+--+++--+-+--+++--+-
+--+-+--+++--+-+--+++--+-+--+-+--+++--+++--+++--+-+--+-+--++
+--+++--+++--+-+--+-+--+++--++---+++--+-+--+-+--+++--+-+--++
+--+-+--+-+--++++-+-+--+++--+-+--+-+--+++--+++--+++--+-+--+-
+--+++--+-+--+++--+-+--+-+--+++--+++--++---+-+--+-+--+++--+-
++-+++--+-+--+-+--+++--+-+--+++--+-+--+-+--+++--+++--+++--+-
+--+-+--+++--+-+--+++-++-+--+-+---++--+++--+++--+-+--+-+--++
+--+-+--+++--+-+--+-+--+++--+-+-++++--+-+--+-+--+++--+++--++
+--+-+--+-+--+++---++--+++--+-+--+-+--+++--+++--+++--+-+--+-
+--+++--+-+--+++--+-++-+-+--+++--+-+--+++--+-+--+----+++--++
+---++--+-+--+-++-+++--+++--+++--+-+--+----+++--+++--+++--+-
+--+-+--+++--+-+--+++-++-+--+-+--+++--+-+--+++--+-+--+-+--++
+--+++--+++--+-+--+-+--+++--+++--+-++-+-+--+-----++--+++--++
+--+-+-++-+--+++--+-+--+++--+-+--+-+--+++--+-+--+++--+-+--+-
+-++++--+++-

These are the primes sent to -1 in this example: 2, 3, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97, 103, 107, 113, 127, 137, 151, 157, 163, 167, 173, 193, 223, 227, 233, 257, 263, 277, 281, 283, 293, 307, 313, 317, 337, 347, 353, 367, 373, 397, 433, 443, 457, 463, 467, 487, 499, 503, 523, 547, 557, 563, 577, 587, 593, 607, 613, 641, 643, 647, 653, 673, 677, 727, 733, 743, 769, 773, 787, 797, 823, 827.

This came from a search initialized by sending primes congruent to 2 or 3 mod 5 to -1 and others to +1.

Note that the only primes not congruent to 2 or 3 that are sent to -1 are 151, 281, 499, 641 and 769. [Are there some that are congruent to 2 or 3 that are sent to 1? If so, which are they?]

Length 819: 

+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-+
+-++--+-++-----+-++-++--+-+++++--+-++--+--+-++--+--+-++-++--
+-++-----+-++-++--+-++-+++-+-+---+--+-++--+--+-++-+++-+-+-+-
+--+-++--++-+-++-+---+-++--+--+-++-++-++-+--+++---++--+--+-+
+--+--+-++-+++-+-++--+--+--++----+-++-+++-+-++--+----++-++--
++++-++--+-++--+--+-++-++--+-+--++--+-++--+---+++--+--+++--+
+--+++---+--+-++-+--+-+++-++--+-++---+-+-++--+--+-++-++--+++
---+--+-+++-+--+--+-+++--+++--+-+--+-++++---++-++--+-++--+--
+-++-+---+-++-++--+-+++-+---++---+--+--++++--+-++--+-++----+
++-+-++-++--+-++--+----++-++--+--+-++--+-+++-+--+-++--+-++-+
+-+---+-++--+--+++--+++-+-++-+---++++--++---++--+--+-++--++-
-+++--+-++-+---+--+--++++-++-+-+----+-+++++--+-+--+---+++++-
+--+-++-+----+++-++--+-++--+--+-+++--+-+--+++---+-++--+--+-+
+-++----++-+++---++-+++-+--+-+--++-++-+

The primes that go to -1 in this example are:

2, 3, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 73, 83, 101, 107, 113, 127, 131, 137, 149, 151, 167, 197, 199, 223, 229, 233, 239, 251, 257, 263, 271, 293, 311, 317, 331, 353, 359, 367, 379, 389, 397, 401, 421, 449, 457, 463, 467, 479, 487, 491, 557, 563, 569, 587, 593, 599, 619, 631, 643, 647, 653, 661, 673, 677, 691, 709, 733, 743, 757, 761, 773, 787, 797, 809, 811

Length 627: 

+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-+
+-++--+-++-----+-++-++--+-+++++--+-++--+--+-++--+--+-++-++--
+-++-----+-++-++--+-++-+++-+-+---+--+-++--+--+-++-+++-+-+-+-
+--+-++--++-+-++-+---+-++--+--+-++-++-++-+--+++---++--+--+-+
+--+--+-++-+++-+-++--+--+--++----+-++-+++-+-++--+----++-++--
++++-++--+-+---+--+-++-++--+-++-++--+-++--+---+++--+--+++--+
+--+++---+--+-++-+--+-+++-++--+-++---+-+-++--+--+-++-++--+++
---+--+-+++-+--+--+-+++--+++--+-+--+-++++---++-++--+-++--+--
+-++-+---+-++-++--+-+++-+---++---+--+--++++--+-++--+-++----+
++-+-++-++--+-++--+----++-++--+--+-++--+-+++-+--+-++--+-++-+
+-+---+-++--+--+++--+++-+++

A sequence of length 545 that agrees with the maximal discrepancy-2 sequences at primes up to and including 67: 

+--+-+--+++--+++--+-+--+++--+-+--+++--++---+-+--+-+-++-+--++
+--+++--+-+--+-+--+-++-+++---++--+-++-++--++--+--++--+++--+-
+-++-+--+-+--+++---++--+-+--+++--+-++--++-+-++--+-+-++-+-+--
+--+++--++--+--++---++-++---++-+--++-++-+--+++--+-+--+++--++
+--+----+++--+-+--+++--+-++-+----+++-++----++++-++--++-+--+-
+-++-++--++---++-++----+--+++-+--+++--+++--+--+-+++--+---+-+
+--++++-----++++--+-++-++--+-++----+-++++----+--+-++-++++-+-
-+---+-++-+-+++----++--+++--+----+-++-+++--++++-+----++++-+-
+--+-++--+-+-+-+--+-+--+++--+++--+-+----+--+++--+++-+--++-++
-+-++

This sequence is -1 at the following primes:

2, 3, 5, 7, 13, 17, 23, 37, 41, 43, 47, 67, 73, 83, 89, 101, 109, 113, 127, 137, 139, 167, 179, 191, 199, 211, 223, 227, 233, 257, 263, 271, 277, 281, 283, 313, 317, 337, 353, 359, 383, 389, 397, 421, 439, 443, 463, 491, 503, 523, 541

General Case

Here is some data on how the discrepancy of completely-multiplicative sequences grows as a function of length, depending on how missing values at prime indices are chosen.

Without loss of generality, one may always set [math]\displaystyle{ x_1=+1 }[/math]

Uniform choice

Here is some data when the values of [math]\displaystyle{ x_n }[/math] are: a given +/-1 sequence when [math]\displaystyle{ n\gt 1 }[/math] is one of the first [math]\displaystyle{ N }[/math] primes, only the value [math]\displaystyle{ -1 }[/math] for [math]\displaystyle{ n }[/math] any other prime, and a multiplicatively computed value when [math]\displaystyle{ n }[/math] is composite.

  • N=1
    • [math]\displaystyle{ x_1=+1 }[/math], [math]\displaystyle{ x_2=+1 }[/math]: D(100)=21, D(1000)=107, D(10000)=407
    • ...
  • N=2
    • [math]\displaystyle{ x_1=+1 }[/math], [math]\displaystyle{ x_2=+1 }[/math], [math]\displaystyle{ x_3=+1 }[/math]: D(100)=34, D(1000)=262, D(10000)=1190
    • ...
  • N=3
    • [math]\displaystyle{ x_1=+1 }[/math], [math]\displaystyle{ x_2=+1 }[/math], [math]\displaystyle{ x_3=+1 }[/math], [math]\displaystyle{ x_5=+1 }[/math]: D(100)=25, D(1000)=413, D(10000)=2332
    • ...

Minimizing the discrepancy D up to the next prime

Here is a plot of D(n), the discrepancy as a function of length, as well as the partial sums of the first few HAP when one starts with [math]\displaystyle{ x_1=1 }[/math] and ask that the value at prime [math]\displaystyle{ p }[/math] be either +1 or -1 depending on which allows to minimize [math]\displaystyle{ D(q) }[/math], where [math]\displaystyle{ q }[/math] is the next prime.

Here is a plot doing the same thing but instead starting with the first 1124 sequence as a seed.

The two plots show that the partial sums do grow at least logarithmically.

Minimizing the sum of partial HAP sums

A method to choose a value at an undertermined prime [math]\displaystyle{ p }[/math] is to choose to impose [math]\displaystyle{ x_p=+1 }[/math] or [math]\displaystyle{ x_p=-1 }[/math] depending on which gave the smallest quantity [math]\displaystyle{ \ell_s(q) }[/math], where [math]\displaystyle{ q }[/math] is the next prime and [math]\displaystyle{ \ell_s(q):=\sum_{d=1}^q s_d(q) }[/math] with [math]\displaystyle{ s_d(q) }[/math] itself the partial sum of the d-HAP up to [math]\displaystyle{ q }[/math].

Here is a plot obtained when setting only [math]\displaystyle{ x_1=+1 }[/math]. On it is shown the function [math]\displaystyle{ f(x):=\log (x) }[/math] (the very flat curve), the partial sums of the sequence and its first few HAPs, and both [math]\displaystyle{ D(n) }[/math] and [math]\displaystyle{ -D(n) }[/math].

Retrieved from "https://michaelnielsen.org/polymath/index.php?title=Multiplicative_sequences&oldid=3010"