Problem 609

[S_r]

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?

[Animus]

It means: count all $\pi$ sequences starting below n+1, that contain exactly k non-primes, e.g. p(4,1)=3.

edit: "non-primes" of course.

[LilStalker]

exactly k non-primes*

[S_r]

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?

[MuthuVeerappanR]

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 non-primes, three of them ((2, 1), (3, 2, 1) and (4, 2)) have exactly one non-prime and (4, 2, 1) has exactly two non-primes.

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

[S_r]

Thank you very much

[clamvin]

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.

[v6ph1]

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.

[clamvin]

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.

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).

[hk]

It's easy to write down the three sequences with 3 non-prime elements: 10,4,2,1; 9,4,2,1 and 8,4,2,1.

[DeKlod]

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