Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have permutation from $x$ to $y$.

And how to make sequence which $d$ summed numbers from this sequence ISN'T a prime number. if we have sequence $x_1,x_2,x_3,x_4,x_5 \dots y$ than $d$ means :
$x_1+x_2+ \dots +x_d$
next pair would be
$x_2+x_3+ \dots +x_{d+1}$
And so on.

for example: permutation from $1$ to $10$ and $d=2$
than we can make lowest lexicographically sequence which is :
$1,3,5,4,2,6,9,7,8,10$
for $x=1$ $y=10$ and $d=3$ we can have :
$1,3,5,4,6,2,10,8,7,9$

This problem is very interesting to me, thanks for any help.

Problem taken from : https://www.spoj.pl/problems/APRIME/

Cheers

share|improve this question
1  
Looks like a backtrack over the greedy algorithm. Put the smallest number in first position, the next smallest in second, and check if the sum is prime. If no, bump the second and continue. If yes, put on the smallest third and check. –  Ross Millikan May 23 '11 at 22:31
    
It doesn't work for x=1 y=7 d=2 we'll have 1,3,5,4,2,6,7 , so we decide to say that we can't make this sentence, but we can. –  Chris May 23 '11 at 22:34
    
No, I meant you keep backtracking until success or you run out of possibilities. Easier to program would be to create a function that lists the permutations in lexicographic order, then checks them in order. As 10! is only 3E6, you can check pretty quickly. –  Ross Millikan May 23 '11 at 23:21
    
I agree that this looks more llike a programming exercise than a math problem, if you want the lexicographically least permutation rather than just any old prime-avoiding permutation. –  Gerry Myerson May 24 '11 at 1:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.