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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
User avatar
S_r
Posts: 32
Joined: Thu Aug 10, 2017 5:37 am

Problem 609

Post 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?
User avatar
Animus
Administrator
Posts: 1919
Joined: Sat Aug 16, 2014 1:23 pm

Re: Problem 609

Post 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.
LilStalker
Posts: 73
Joined: Thu Nov 03, 2016 4:32 pm

Re: Problem 609

Post by LilStalker »

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

Re: Problem 609

Post 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?
MuthuVeerappanR
Posts: 483
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Problem 609

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

Re: Problem 609

Post by S_r »

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

Re: Problem 609

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

Re: Problem 609

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

Re: Problem 609

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

Re: Problem 609

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

Re: Problem 609

Post 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 :-)
Post Reply