[seqfan] Re: wanted: solution to a recurrence

[hv at crypt.org]

"N. J. A. Sloane" <njas at research.att.com> wrote:
:I'm looking for a sequence a(1), a(2), ..., not all 1's, 
:that satisfies the forward-looking recurrence
:a(n+1) = a(a(n)+n+1) for n>= 1.
:
:In fact I would like the earliest such sequence.
[...]
:Can someone produce an explicit sequence satisfying the recurrence?
:The first term might be 1. The entries should be positive
:integers, not all 1's.

With subsequent corrections, I'd characterize this as:

1) Given a(n) = k, we require min(m: a(n+m) = k, m > 0) = k+1.

Then:

2) If a(1) = a(2) = 1, we find by induction that a(n) = 1 for all n. So
we can't allow that.

3) For n > 1, if a(n) = k then a(n+b_n(i)) = k for all i, with b_n(0) = 0
and b_n(i+1) = b_n(i) + a(n+b_n(i)-1). Hence every such k appears infinitely
often.

4) Hence, any a(n) not forced to be equal to a previous a(m) must have
some new, never-seen-before value (or violate (1)). Whether such force
exists is completely determined by the a(m): 1 <= m < n.

5) We can fully characterize a valid sequence by C = [ c_i ], the distinct
values that it takes in order of first appearance. We can then generate
the original sequence using (1) and (4). The desired sequence is that
generated by the lexically earliest C.

6) Given a(n) = k, we must avoid a(n+m) = k-m for all m > 0, else we'd
have a(n+1) = a(n+1+k) = a(n+m+1), violating (1).

7) Given known a(n-1) = x, a(n+1) = y and trying to find a(n) = k, we have
a(n+1) = a(n+k+1) = y. So by (6) and (3) we must avoid b_n(i) = y+1 for
all i.

A simple approach to generating C without backtracking first fails (7)
at [1, 2, 4, 6, 9, 10], at which point we have the sequence:
  a(i) = [ 1, 2, 2, 4, 2, 4, 6, 4, 2, 9, 6, 9, 2, 4, 10, 4, ?, 9, ?, 6, ... ]
At this point setting a(17) = k gives a(k+19)=a(k+28) but also a(28)=a(k+28).
This defect is introduced by the 9, so C >= [1, 2, 4, 6, 10, ...].

So I wrote code based on the assumption that defending against both (6)
and (7) would be sufficient to avoid backtracking. That seems to work,
and I find the sequence below. I am quite nervous about the logic of my code
though, so I'd welcome verification.

C = [ 1 2 4 6 11 12 16 14 24 29 9 32 23 38 8 41 26 40 43 42 71 35 53 47 58 64
 20 37 84 50 62 76 34 70 101 122 44 92 117 59 5 102 88 98 93 96 119 19 133
 104 128 146 78 145 151 157 94 180 134 148 139 144 150 166 160 161 123 83 107
 121 179 173 130 185 143 13 210 177 188 205 199 141 209 158 175 283 217 251
 249 52 214 202 208 231 207 256 307 154 212 7 240 264 243 247 172 290 246 282
 222 254 308 48 56 253 303 311 331 295 310 269 277 170 60 328 293 259 390 233
 215 198 365 326 263 49 320 398 342 332 111 280 404 406 294 355 405 344 127
 242 167 292 258 156 192 347 352 370 267 262 171 377 340 428 505 367 395 375
 288 287 312 362 193 372 444 306 411 413 414 386 85 296 270 378 410 97 266
 309 412 371 274 396 456 512 434 399 576 609 525 219 509 624 241 354 470 383
 472 684 315 393 380 334 400 336 594 490 675 531 426 323 341 421 140 569 462
 392 402 445 730 610 63 683 229 488 606 504 275 387 368 568 666 552 430 300
 497 479 570 667 197 574 678 401 481 582 ... ]

a() = [ 1 2 2 4 2 4 6 4 2 11 6 11 2 4 12 4 16 11 12 14 16 6 24 2 29 9 29 4 24
 12 32 14 24 11 16 29 23 6 38 8 41 26 32 40 38 16 24 2 41 43 41 29 42 12 9 71
 4 11 35 53 6 11 24 14 71 23 9 11 32 35 47 2 58 24 58 40 11 8 71 32 64 42 26
 16 38 20 71 14 8 9 43 37 29 41 53 12 84 9 58 43 38 35 8 50 62 47 71 58 84 16
 76 50 64 6 34 70 11 101 2 122 34 122 41 20 26 44 76 4 101 29 92 24 101 40 37
 53 23 8 117 35 59 5 102 38 26 42 117 102 12 70 32 44 88 71 62 122 101 43 14
 92 8 70 64 98 20 93 84 47 96 70 76 42 53 92 37 59 119 6 58 19 133 9 26 44 58
 93 11 50 117 23 104 26 128 16 146 78 88 145 50 133 5 14 151 4 157 94 14 180
 157 44 146 134 59 104 53 96 151 122 128 2 32 180 32 24 148 62 92 98 58 139
 29 144 64 150 40 119 166 19 117 160 76 71 34 93 41 38 161 42 148 133 12 47 8
 180 146 24 35 117 43 84 144 180 20 47 102 70 37 123 96 83 107 121 104 179 88
 119 173 93 101 11 35 130 185 47 161 145 38 139 92 143 148 35 117 13 210 26 6
 150 177 8 14 188 84 150 123 205 23 210 14 199 141 102 151 34 9 188 130 71 53
 98 209 16 6 199 188 139 58 117 158 199 210 161 175 5 283 217 37 41 6 283 128
 78 251 50 144 283 59 2 9 249 9 52 214 107 4 166 160 134 249 166 52 202 94
 119 208 83 44 70 122 29 231 101 98 62 41 43 64 179 121 6 11 143 207 12 40
 117 11 150 157 53 256 96 143 104 144 173 40 133 150 231 76 24 32 19 214 180
 2 307 42 307 13 70 185 202 151 154 43 212 209 64 251 7 240 214 70 117 32 92
 205 240 264 38 243 148 146 19 41 133 122 35 247 179 20 256 172 158 145 71 177
 44 93 307 102 88 123 41 290 119 246 92 212 4 282 256 34 58 282 222 47 78 243
 62 254 98 308 247 8 24 133 48 56 253 185 208 251 24 303 199 143 283 84 29 249
 175 93 117 311 290 144 58 6 331 133 11 130 26 295 331 5 141 303 23 310 ... ]

I guess the next question will be: is C a permutation of the integers? I have
no idea on that: 5 and 7 turn up quite late, but 3 hasn't shown yet.

Also maybe of interest is the sequence of indices in a() at which the new
values are introduced. And maybe also the sequence P_2 = [m: a(m) = 2], the
simplest example of a path of repeated k.

For what it's worth, my mostly uncommented perl code is available at
<http://crypt.org/hv/maths/sloane-0.01>. It generates numbers surprisingly
fast - it'd be no trouble to produce a few thousand terms of either seq.

Hugo