Permutations, Fractions, Primes

[Joseph Biberstine]

(Inspired by your quickly found maximal example for n=6)

This slightly modified code finds the number of maximal permutations:
Table[Length[Last[Split[Sort[Map[Length[Select[#, PrimeQ[#] &]] &, 
Map[Join[Numerator /@ #, Denominator /@ #] &, Map[Table[Sum[1/#[[k]], 
{k, 1, m}], {m, 1, Length[#]}] &, Permutations[Range[n]]]]]]]]], {n, 1, 9}]

Sequences begins (from n=1):
{1, 1, 1, 2, 2, 2, 8, 28, 80}

OEIS absent.

Compare to naive maximum (n! from n=1):
{1, 2, 6, 24, 120, 720, 5040, 40320, 362880}

The share of maximal permutations among all permutations for n=1 through 
n=9 are each unit fractions.  The corresponding reciprocals begin:
{1, 2, 6, 12, 60, 360, 630, 1440, 4536}

OEIS absent.

This code gives all maximal permutations for a range of n:
score[p_List] := Module[{ps}, ps = Table[Sum[1/p[[k]], {k, 1, m}], {m, 
1, Length[p]}]; Length[Select[Join[Numerator /@ ps, Denominator /@ ps], 
PrimeQ[#] &]]];
maxlst = {0, 3, 4, 4, 6, 8, 8, 10, 11};
Table[Select[Permutations[Range[n]], score[#] == maxlst[[n]] &], {n, 1, 8}]

All maximal permutations for n=6:
{{2, 1, 6, 3, 5, 4}, {2, 6, 1, 3, 5, 4}}

So we see you're quite lucky.

I won't cloud this message with that output list of maximal permutations 
for each n, but the above code reveals stabilizing patterns as n grows. 
  For n=2 through at least n=8, all permutations begin with 2.  For n=6 
through at least n=8, all permutations begin {2,1,6} or {2,6,1}, 
corresponding to partial sums {1/2, 3/2, 5/3} and {1/2, 2/3, 5/3}.  So 
for one, n>=6 gives 2n >= score >= 5.

Attached is a graph that attempts to express emerging patterns.  It's a 
somewhat confusing illustration.  It overlays the list plots of all 
maximal permutations on 1<=n<=8, with jitter uniform on [-1/4,1/4].  So 
it clumsily shows expected bunching near coordinates, e.g., {1,2}, 
{2,1}, {2,6}, {3,1}, and {3,6}.  Notice e.g. in this n range that 3 
seems particularly permutable.

-JRB

Leroy Quet wrote:
> Joseph Biberstine wrote:
>> Naive Mathematica one-liner:
>> Table[Max[Map[Length[Select[#, PrimeQ[#] &]] &, Map[Join[Numerator /@ #, 
>> Denominator /@ #] &, Map[Table[Sum[1/#[[k]], {k, 1, m}], {m, 1, 
>> Length[#]}] &, Permutations[Range[n]]]]]], {n, 1, 9}]
>>
>> Sequences begins (from n=1):
>> {0, 3, 4, 4, 6, 8, 8, 10, 11}
>>
>> OEIS absent already.
>>
>> A naive maximum: 2n :)
>>
>> -JRB
>>
>> Leroy Quet wrote (in part): 
>>> First, take a permutation {b(k)} of the first n positive integers, and 
>>> then take the partial sums,...
> 
>> ....
>  
>>> If we make a game of this, a better player might play the permutation
>>> (2,6,1,4,5,3),
>>>
>>> which gives the s(m)'s
>>> 1/2, 2/3, 5/3, 23/12, 127/60, 49/20.
>>>
>>>
>>> So we have the primes: 2,2,3,5,3,23,127, for a score of 7.
>>>
>>> My question is, what is the maximum possible score for each given n?
>>>
>>> I get the sequence beginning
>>> 0,3,4,4,...
> 
> I see that Joseph Biberstine has computed an 8 for the 6th term.
> So I was encouraged to find an n=6 permutation that gives a score of 8.
> (Luckily, I found a permutation relatively quickly.)
> 
> 2,6,1,3,5,4
> 
> The s(m)'s:
> 1/2,2/3,5/3,2/1,11/5,49/20.
> 
> (Yay!)
> 
> I would ask someone to compute more terms so this sequence can be 
> submitted to the EIS, but, as is the case wih many game-derived 
> sequences, the relatively long explanation of the sequence may make it 
> too esoteric to be interesting to a general audience.
> 
> Thanks,
> Leroy Quet
-------------- next part --------------
A non-text attachment was scrubbed...
Name: jitterplot.png
Type: image/png
Size: 11829 bytes
Desc: not available
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061223/962ae069/attachment-0003.png>