[ASSIGNMENT] Super Prime Numbers

Question

The number X is called Super Prime if it is Prime and can be represented as:
X = 2^n+3^m, where n,m - non-negative integers

Task 1:
Write a function isSuperPrime(X) which checks X and returns True or False

NOTE:
Brut-force solution is acceptable, but not the best one.

Task 2:
Print out all Super Prime numbers from a given range [A,B]

NOTE:
Solution, which checks one by one numbers from range [A,B] using a function from task 1, is acceptable BUT not optimal. I highly recommend to find a better one!

Answer 1

Well, one week past from the day when the assignment was published.
Here is my own solution for it:

https://code.sololearn.com/c8rDpTnjVudj/?ref=app

It doesn't pretend to be the best one. I found all the solutions published here at this moment (@VcC, @John Wells, @Russ, @LukArToDo) to be good and correct. You can refer to them to see different approaches (demonstrating different complexity of used algorithms) to resolve the challenge.

My own idea on which this challenge is based is described in the comments to my code. In brief:

Task 1:
You need to check that the number is Prime and is Super (here and further it means that it can be represented as N=2^n+3^m).
Complexity of simple Prime check is O(sqrt(N)).
Complexity of usual Super check is O(log3(N)).
Complexity of the best Super check is O(1)!

Task 2:
Complexity using results of Task 1 consequently for all numbers in a range ~ O(N^(3/2)).
Complexity with "in advance" lists generation ~ O(N*log(log(N))).

Answer 2

https://code.sololearn.com/cR0qNN7lBLlT/?ref=app

Answer 3

I'm not so happy with my solution, but...
https://code.sololearn.com/c0Jia6wt1a2C/?ref=app

Answer 4

Try this again. I changed something and saved accidently.
https://code.sololearn.com/ccP70V7N5EjR

Answer 5

My attempt for both tasks. Not sure how I feel about it...

Thanks for the challenge.

https://code.sololearn.com/cTl39gip0ReS/?ref=app

Edit: code now improved thanks to input from @Nevfy.

Answer 6

i think i won the challenge

https://code.sololearn.com/cL0S91MlGG1M/?ref=app

Answer 7

I thought Super Prime numbers are a subset of prime numbers occupying prime numbered positions in the ascending list of all prime numbers?

Answer 8

@seetho Yes, you right, thanks! I completely forgot about these ones. However, I use more often "Prime-indexed Primes" name for them.
For that particular task: I just invented this type of numbers presented above and I didn't know how to call them, so I just called them Super Prime. That can be a bit confusing so I will probably change the name...

Answer 9

Good trick for the 2n+3p test ! Should have digged deeper in the math but not easy on a mobile screen.. For task2 the method used by Russ and me is not in advance list generation (caching) but real time list generation (ie not scanning all numbers but just going to the ones relevant). Which i think is the fastest solution.