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