P609
projecteuler.net

π Sequences

ℹ️Published on Saturday, 9th September 2017, 04:00 pm; Solved by 1033;
Difficulty rating: 20%

For every n1 the prime-counting function π(n) is equal to the number of primes not exceeding n.
E.g. π(6)=3 and π(100)=25.

We say that a sequence of integers u=(u0,,um) is a π sequence if

  • un1 for every n
  • un+1=π(un)
  • u has two or more elements

For u0=10 there are three distinct π sequences: (10,4), (10,4,2) and (10,4,2,1).

Let c(u) be the number of elements of u that are not prime.
Let p(n,k) be the number of π sequences u for which u0n and c(u)=k.
Let P(n) be the product of all p(n,k) that are larger than 0.
You are given: P(10)=3×8×9×3=648 and P(100)=31038676032.

Find P(108). Give your answer modulo 1000000007.



Soluzione

Last modified: June 14, 2025. Website built with Franklin.jl and the lovely Julia programming language.