Cody Problems 60942, 60943, and 60944 involve polynomials that generate primes. No polynomial can generate only prime numbers, but some can generate sizable runs of primes. For example, for n = 0, 1, 2,…,10, 
produces 11, 13, 19, 29, 43, 61, 83, 109, 139, 173, and 211, which are all prime. For 
, both terms in the polynomial are divisible by 11, and the result (253) is composite.
produces 11, 13, 19, 29, 43, 61, 83, 109, 139, 173, and 211, which are all prime. For , both terms in the polynomial are divisible by 11, and the result (253) is composite. Write a function that takes the coefficients of the polynomial in standard Matlab form (i.e., a vector with the coefficients in order of decreasing order of the terms) and returns the length of the longest run of primes as well as a sorted list (low to high) of the distinct primes in the run. Please note the following:
- Take the absolute value of the output of the polynomial. For example, consider -11, -13, -19, etc. to be prime for this problem, even though negative numbers are not strictly considered to be prime.
- Round the absolute value to the nearest integer. Although this step is not necessary when the coefficients of the polynomial are integers, it can be necessary when they are not, as in the last two tests.
- Make sure to list only the primes in the longest run. The polynomials will produce other primes outside of the longest run, but do not include them in the output.
Solution Stats
Problem Comments
3 Comments
Solution Comments
Show comments
Loading...
Problem Recent Solvers6
Suggested Problems
More from this Author321
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
This is an interesting and nice problem, Chris. Difficulty is of course how to know a run is the longest !
Thanks Nicolas. I added a link to the MathWorld page that listed the polynomials in the test. Perhaps I misinterpreted that page as giving the longest runs. For the example in the description, every value of n divisible by 11 will give a composite number, so the runs can be no longer than 11 terms. Similar arguments apply to at least some of the other examples, though I haven't worked out all of them.
Cool problem. I wonder if there are any polynomials where the longest run of primes does not begin at an input of x=0? It would make the problem a little more difficult.