We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
For those who passed all test cases, could you please give a hint on whether we should approach this problem by
Iterating on starting from to (+= 2 and skipping multiples of ) and feed them to primality testing (e.g. Miller-Rabin), or
Generating all composite numbers from primes except and ? (e.g. using a heap)
Do we need to make use of the observation that is the least common multiple between and if ?
I was using the first approach and only passed the first 6 test cases. My implementataion of the A(i) function was by performing curr = (curr * 10 + 1) % i on each iteration step, and the upper bound of this function is which is not very nice.
EDIT: An observation, that for example , where is one of the valid answers, but , and are all invalid answers. I wonder if there is any pattern there. Also, it is curious that is the largest prime we need for up to .
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #130: Composites with prime repunit property
You are viewing a single comment's thread. Return to all comments →
For those who passed all test cases, could you please give a hint on whether we should approach this problem by
Iterating on starting from to (
+= 2and skipping multiples of ) and feed them to primality testing (e.g. Miller-Rabin), orGenerating all composite numbers from primes except and ? (e.g. using a heap)
Do we need to make use of the observation that is the least common multiple between and if ?
I was using the first approach and only passed the first 6 test cases. My implementataion of the
A(i)function was by performingcurr = (curr * 10 + 1) % ion each iteration step, and the upper bound of this function is which is not very nice.EDIT: An observation, that for example , where is one of the valid answers, but , and are all invalid answers. I wonder if there is any pattern there. Also, it is curious that is the largest prime we need for up to .