Problem 609
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
In particular don't post any code fragments or results.
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Problem 609
I didn't understand the following line :
Let p(n,k) be the number of π sequences u for which $u_0$ ≤n and c(u)=k .
can you please clear it to me with a suitable example?
Let p(n,k) be the number of π sequences u for which $u_0$ ≤n and c(u)=k .
can you please clear it to me with a suitable example?
Re: Problem 609
It means: count all $\pi$ sequences starting below n+1, that contain exactly k nonprimes, e.g. p(4,1)=3.
edit: "nonprimes" of course.
edit: "nonprimes" of course.
Re: Problem 609
You mean if n=4 then following pi sequences can be created
4,2,1 and 4,2 and only one of them have one not prime, k=c(u), which is 4,2.
Is it? Correct me if I'm wrong.
If that's correct help me with last doubt. Who will choose values of n and k?
4,2,1 and 4,2 and only one of them have one not prime, k=c(u), which is 4,2.
Is it? Correct me if I'm wrong.
If that's correct help me with last doubt. Who will choose values of n and k?

 Posts: 492
 Joined: Sun Mar 22, 2015 2:30 pm
 Location: India
 Contact:
Re: Problem 609
p(n, k) is defined for all initial values less than or equal to 'n'.
So when n = 4, the pi sequences are
(2, 1), (3, 2), (3, 2, 1), (4, 2) and (4, 2, 1).
Of these (3, 2) has 0 nonprimes, three of them ((2, 1), (3, 2, 1) and (4, 2)) have exactly one nonprime and (4, 2, 1) has exactly two nonprimes.
p(4, 0) = 1, p(4, 1) = 3, p(4, 2) = 1 and p(4, k) = 0 for k > 2.
P(n) = P(4) = 1 x 3 x 1 = 3
So when n = 4, the pi sequences are
(2, 1), (3, 2), (3, 2, 1), (4, 2) and (4, 2, 1).
Of these (3, 2) has 0 nonprimes, three of them ((2, 1), (3, 2, 1) and (4, 2)) have exactly one nonprime and (4, 2, 1) has exactly two nonprimes.
p(4, 0) = 1, p(4, 1) = 3, p(4, 2) = 1 and p(4, k) = 0 for k > 2.
P(n) = P(4) = 1 x 3 x 1 = 3
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
Re: Problem 609
Does anyone know if the given P(10) was correct? My program accurately gives P(100) as 31038676032, but gives P(10) = 3 * 11 * 8 * 2 = 528, which is different than the provided P(10). I hand checked P(10) too and 3 * 11 * 8 * 2 seems to be correct.
Re: Problem 609
It is  I checked it again.
And your total number of sequences differs by 1:
2 generates 1 sequence (2,1)
3 and 4 generate (3,2,1), (3,2) and the same with 4 at the first position
5 to 10 generate 3 sequences each: 5 and 6 with 3 as next and 7 to 10 with 4 as next.
So I have 1 + 2*2 + 6*3 = 23 sequences.
You have 24.
And your total number of sequences differs by 1:
2 generates 1 sequence (2,1)
3 and 4 generate (3,2,1), (3,2) and the same with 4 at the first position
5 to 10 generate 3 sequences each: 5 and 6 with 3 as next and 7 to 10 with 4 as next.
So I have 1 + 2*2 + 6*3 = 23 sequences.
You have 24.
Re: Problem 609
Hm, weird, because I actually just got my program to run correctly for P(10^8) and matched the solution, but it still fails for P(10).v6ph1 wrote: ↑Fri Sep 22, 2017 2:52 pm It is  I checked it again.
And your total number of sequences differs by 1:
2 generates 1 sequence (2,1)
3 and 4 generate (3,2,1), (3,2) and the same with 4 at the first position
5 to 10 generate 3 sequences each: 5 and 6 with 3 as next and 7 to 10 with 4 as next.
So I have 1 + 2*2 + 6*3 = 23 sequences.
You have 24.
Re: Problem 609
It's easy to write down the three sequences with 3 nonprime elements: 10,4,2,1; 9,4,2,1 and 8,4,2,1.
Re: Problem 609
Hi all,
I was wondering whether someone would be good enough to check the following values for me (all given modulo 1'000'000'007):
P(1000) = Values removed by moderator
P(10'000) =
P(100'000) =
P(1'000'000) =
P(10'000'000) =
Thanks in advance!
Claude
EDIT: Disregard this, everyone... I missed a modulo in my final step so that my numbers overflowed. Sorted that out and now the answer for 10^8 is correct, so I'll assume my intermediate values are too
I was wondering whether someone would be good enough to check the following values for me (all given modulo 1'000'000'007):
P(1000) = Values removed by moderator
P(10'000) =
P(100'000) =
P(1'000'000) =
P(10'000'000) =
Thanks in advance!
Claude
EDIT: Disregard this, everyone... I missed a modulo in my final step so that my numbers overflowed. Sorted that out and now the answer for 10^8 is correct, so I'll assume my intermediate values are too