## Problem 609

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
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.

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 post any spoilers
S_r
Posts: 32
Joined: Thu Aug 10, 2017 5:37 am

### 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?
Animus
Posts: 1926
Joined: Sat Aug 16, 2014 1:23 pm

### Re: Problem 609

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
Posts: 74
Joined: Thu Nov 03, 2016 4:32 pm

### Re: Problem 609

exactly k non-primes* S_r
Posts: 32
Joined: Thu Aug 10, 2017 5:37 am

### 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?
MuthuVeerappanR
Posts: 493
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 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 It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
S_r
Posts: 32
Joined: Thu Aug 10, 2017 5:37 am

### Re: Problem 609

Thank you very much
clamvin
Posts: 2
Joined: Fri Sep 22, 2017 12:51 pm

### 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.
v6ph1
Posts: 131
Joined: Mon Aug 25, 2014 7:14 pm

### 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. clamvin
Posts: 2
Joined: Fri Sep 22, 2017 12:51 pm

### Re: Problem 609

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).
hk
Posts: 11286
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: Problem 609

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
Posts: 19
Joined: Tue Aug 21, 2018 8:55 am

### 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) =
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 