Delete comment from: Computational Complexity
Here is a not too difficult argument for an upper bound of 83.
Let A be the set of primes greater than 25, and their multiples. There are 24 such numbers (16 primes, 6 twice a prime, and 2 three times a prime).
Note that everytime we "exit" A, it must be through {1,2,3}. Let B be the complement of (S3 U {1,2,3}).
So, removing {1,2,3} from our path we get at most four "segments", each of which is solely in A or solely in B.
Now, if we only have A-segments, then the whole path has size at most 27, so we exclude this case.
So there are at most three A-segments.
By considering the graph induced on A, we see that an A-segment can have at most 3 vertices in it, and this can only happen by taking something of the form 2p-p-3p, for p a prime between 25 and 33. In particular, such a segment must end with both 2 and 3, so we can only have one A-segment of length 3.
The other 2 A-segments can have length at most 2, so we can use at most 7 vertices from A.
This gives an upper bound of 100-(24-7)=83.
The same argument with {1,2} istead of {1,2,3} gives a bound of 86. I'm guessing going to {1,2,3,4} will improve it further still, and with a bit of case-work, one might be able to get 77 by hand.
Sep 18, 2017, 4:16:43 AM