Page **1** of **1**

### Problem 609

Posted: **Mon Sep 11, 2017 8:18 am**

by **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?

### Re: Problem 609

Posted: **Mon Sep 11, 2017 10:55 am**

by **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.

### Re: Problem 609

Posted: **Mon Sep 11, 2017 1:47 pm**

by **LilStalker**

exactly k non-primes*

### Re: Problem 609

Posted: **Mon Sep 11, 2017 6:18 pm**

by **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?

### Re: Problem 609

Posted: **Mon Sep 11, 2017 6:58 pm**

by **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

### Re: Problem 609

Posted: **Tue Sep 12, 2017 3:42 am**

by **S_r**

Thank you very much

### Re: Problem 609

Posted: **Fri Sep 22, 2017 12:55 pm**

by **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.

### Re: Problem 609

Posted: **Fri Sep 22, 2017 2:52 pm**

by **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.

### Re: Problem 609

Posted: **Fri Sep 22, 2017 3:22 pm**

by **clamvin**

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.

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

### Re: Problem 609

Posted: **Sat Sep 23, 2017 3:21 pm**

by **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.

### Re: Problem 609

Posted: **Mon Oct 01, 2018 12:34 pm**

by **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