- don't play too many songs from the same artist in a row (and too many is probably 2) - don't play too many slow/fast/sad/angry/... songs in a row - ... instruments - ... genres - ... "feel" - ...
Deep AI is definitely needed to create playlists that "feel random". :)
The prime method will sample songs p apart from each other, and it's easy to find examples of N and p where p is even, for example N=5 p=2. More generally, this method works for any n that is co-prime with N, so N=5 n=4 works as well.
There are lots of shufflings where subsequent songs are not separated by a constant amount, so your main point is true. There are many combinations of songs that you would never hear no matter which prime you picked.
To quantify just how many takes a little bit of work.
There are N! total shufflings possible. We know that there are N-1 or less numbers that are co-prime with N (you get N-1 when N is prime, less otherwise). For each number that is co-prime, we have N possible shufflings, each starting from a different point. This gives at most N(N-1) shufflings from the prime method (really the co-prime method).
As a percentage of total shufflings, we know the upper bound from the co-prime method is N(N-1) / N! == 1/(N-2)!. This very quickly goes to 0. For the first few N,
N % of shuffles
2 100.00000%
3 100.00000%
4 50.00000%
5 16.66667%
6 4.16667%
7 0.83333%
8 0.13889%
9 0.01984%
10 0.00248%
11 0.00028%
12 0.00003%
13 0.00000%
So for any reasonable number of songs, we know that _most_ shufflings will not be found by the prime shuffling method.
Another method is to pick a random key K and sort the entries of the playlist based on HMAC(SONG, K) (where SONG is the name or other identifier of the song). This has a number of interesting properties. For starters the playlist will be randomized (that's good). It will also keep it's overall order if a new song is added. The new song will get inserted based upon its HMAC. You can switch things up a bit by having K be a based on the current date. That way new songs will maintain their order and jumping to a track on a given day will continue the chain as before, but day to day you won't always hear the same tracks back to back.