a(1) = 1 is the smallest available choice at that point and does not lead to a contradiction. It means that after this term, the term at index 1 + 1 = 2 must be visited.
a(2) cannot be a prime since these are >= 2 and would "point" to a nonpositive index. The smallest available choice is a(2) = 4, which means that after this term, the term at index 2 + 4 = 6 must be visited.
a(3) also cannot be prime, because 2 would lead back to 3  2 = 1 and give a loop, and other primes are too large to specify a valid step to the left. Thus a(3) = 6 is the smallest possible choice, leading to index 3 + 6 = 9 after this term is visited.
Similarly a(4) = 8, leading to index 4 + 8 = 12 after this term.
Then a(5) can be equal to the smallest available number, 2, leading to index 5  2 = 3 after this term is visited.
Therefore a(6) cannot be 3, which would lead to 6  3 = 3, but a(3) already has a(5) as predecessor. Larger primes aren't possible either, so the smallest possible choice is a(6) = 9, leading to 6 + 9 = 15.
And so on.
After 1000 terms, the smallest unused number is the prime 787, and the earliest term which does not yet have a predecessor is a(226) = 238.
After 2000 terms, the smallest unused number is the prime 1583, and the earliest term which does not yet have a predecessor is a(420).
After 10^4 terms, the smallest unused number is the prime 8219, and the earliest term which does not yet have a predecessor is a(1784).
It appears that these limits increase roughly linearly, which justifies the conjecture that all numbers will eventually appear and have a predecessor.
The trajectories involving the first few terms are:
a(1)=1 > a(2)=4 > a(6)=9 > a(15)=18 > a(33)=36 > a(69)=76 > a(145)=103 > a(42)=48 > a(90)=96 > a(186)=200 > a(386)=404 > a(790)=820 > a(1610)=1666 > a(3276)=3369 > a(6645)=6807 > ...
... > a(6461)=5261 > a(1200)=937 > a(263)=193 > a(70)=47 > a(23)=13 >
a(10)=5 > a(5)=2 > a(3)=6 > a(9)=12 > a(21)=25 > a(46)=51 > a(97)=67 >
a(30)=34 > a(64)=70 > a(134)=144 > a(278)=294 > a(572)=596 >
a(1168)=1210 > a(2378)=2451 > a(4829)=3907 > a(922)=957 > a(1879)=1939 >
a(3818)=3922 > a(7740)=7917 > ...
... > a(4286)=3461 > a(825)=858 > a(1683)=1737 > a(3420)=2741 > a(679)=708 >
a(1387)=1087 > a(300)=223 > a(77)=53 > a(24)=27 > a(51)=56 >
a(107)=116 > a(223)=163 > a(60)=66 > a(126)=89 > a(37)=23 > a(14)=7 >
a(7)=3 > a(4)=8 > a(12)=15 > a(27)=32 > a(59)=65 > a(124)=133 >
a(257)=273 > a(530)=552 > a(1082)=1124 > a(2206)=2271 > a(4477)=4593 >
a(9070)=9275 > ...
We can modify the sequence from a certain index on, in order connect the trajectories through a(3) = 6 and a(4) = 8 earlier. For example, one variant which has the same terms up to a(10) but connects all these quite early yields (breaking lines before "local minima"):
a(1)=1 > a(2)=4 > a(6)=9 > a(15)=7 > a(8)=10 > a(18)=11 >
a(7)=3 > a(4)=8 > a(12)=14 > a(26)=13 > a(13)=15 > a(28)=17 >
a(11)=16 > a(27)=18 > a(45)=31 >
a(14)=20 > a(34)=21 > a(55)=23 > a(32)=22 > a(54)=37 > a(17)=24 >
a(41)=19 > a(22)=25 > a(47)=26 > a(73)=53 >
a(20)=28 > a(48)=29 > a(19)=27 > a(46)=30 > a(76)=47 >
a(29)=32 > a(61)=33 > a(94)=71 > a(23)=34 > a(57)=41 >
a(16)=35 > a(51)=36 > a(87)=43 > a(44)=38 > a(82)=39 > a(121)=97 >
a(24)=40 > a(64)=42 > a(106)=73 > a(33)=44 > a(77)=67 > a(10)=5 >
a(5)=2 > a(3)=6 > a(9)=12 > a(21)=45 > ...
