P734
projecteuler.net

A Bit of Prime

ℹ️Published on Saturday, 14th November 2020, 07:00 pm; Solved by 363;
Difficulty rating: 35%

The logical-OR of two bits is 0 if both bits are 0, otherwise it is 1.
The bitwise-OR of two positive integers performs a logical-OR operation on each pair of corresponding bits in the binary expansion of its inputs.

For example, the bitwise-OR of 10 and 6 is 14 because 10=10102, 6=01102 and 14=11102.

Let T(n,k) be the number of k-tuples (x1,x2,,xk) such that

  • every xi is a prime n
  • the bitwise-OR of the tuple is a prime n

For example, T(5,2)=5. The five 2-tuples are (2,2), (2,3), (3,2), (3,3) and (5,5).

You are given T(100,3)=3355 and T(1000,10)2071632(mod1000000007).

Find T(106,999983). Give your answer modulo 1000000007.



Soluzione

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