A special type of prime is generated by the formula `p = 2^m * 3^n + 1` where `m` and `n` can be any non-negative integer.

The first `5` of these primes are `2, 3, 5, 7, 13`, and are generated as follows: 
```Haskell
2 = 2^0 * 3^0 + 1
3 = 2^1 * 3^0 + 1
5 = 2^2 * 3^0 + 1
7 = 2^1 * 3^1 + 1
13 = 2^2 * 3^1 + 1
..and so on
```
You will be given a range and your task is to return the number of primes that have this property. For example, `solve(0,15) = 5`, because there are only `5` such primes `>= 0 and < 15`; they are `2,3,5,7,13`. The upper limit of the tests will not exceed `1,500,000`.

More examples in the test cases. 

Good luck!

If you like Prime Katas, you will enjoy this Kata: [Simple Prime Streaming](https://www.codewars.com/kata/5a908da30025e995880000e3)

Difficulty: introductory

Starter code:

def solve(x, y):
	

Solutions:
sb_primes = [2, 3, 5, 7, 13, 17, 19, 37, 73, 97, 109, 163, 193, 257, 433, 487, 577, 769, 1153, 1297, 1459, 2593, 2917, 3457, 3889, 10369, 12289, 17497, 18433, 39367, 52489, 65537, 139969, 147457, 209953, 331777, 472393, 629857, 746497, 786433, 839809, 995329, 1179649, 1492993]

def solve(x, y):
    return sum(x <= p < y for p in sb_primes)

def is_prime(n): return all(n%p!=0 for p in range(2,int(n**0.5)+1))
stone = []

for i in range(20):
    for j in range(12):
        p = (2**i)*(3**j) + 1
        if is_prime(p): stone.append(p)

def solve(x,y):
    return sum(1 for p in stone if p>=x and p<y)

specials = (2, 3, 5, 7, 13, 17, 19, 37, 73, 97, 109, 163, 193, 257, 433, 487,
            577, 769, 1153, 1297, 1459, 2593, 2917, 3457, 3889, 10369, 12289,
            17497, 18433, 39367, 52489, 65537, 139969, 147457, 209953, 331777,
            472393, 629857, 746497, 786433, 839809, 995329, 1179649, 1492993)


def solve(i, j):
    return sum(1 for n in specials if i <= n <= j)

from itertools import compress
from math import log
import numpy as np

n = 1_500_000
s = np.ones(n, dtype=int)
s[:2] = s[4::2] = 0
for i in range(3, int(len(s)**0.5)+1, 2):
    if s[i]:
        s[i*i::i] = 0
ps = set(compress(range(len(s)), s))
stone_bridge_primes = set()
for i in range(int(log(n, 2))+1):
    for j in range(int(log(n, 3))+1):
        x = 2**i * 3**j + 1
        if x in ps:
            stone_bridge_primes.add(x)
sbp = sorted(stone_bridge_primes)

def solve(x,y):
    return np.searchsorted(sbp, y) - np.searchsorted(sbp, x)

def isprime(n):
    if n==2: return True
    if n%2==0 or n<2: return False
    for i in range(3,int(n**0.5)+1,2):
        if n%i==0:
            return False 
    return True
sbs = []
for i in range(22):
    j = 0
    while 2**i * 3**j + 1 <= 1500000:
        if isprime(2**i * 3**j + 1):
            sbs.append(2**i * 3**j + 1)
        j += 1
def solve(x,y): return sum( x <= z & z <= y for z in sbs )

from bisect import bisect_left as bisect
from math import log

def isPrime(n): return n==2 or n%2 and all(n%p for p in range(3, int(n**.5)+1, 2))

MAX    = 1500000
mPow2  = int(log(MAX,2))
STONES = sorted(n for n in { 2**n2 * 3**n3 + 1 for n2 in range(mPow2+1)
                                               for n3 in range(int(log(MAX // 2**n2,3))+1) }
                  if isPrime(n))


def solve(x,y):
    low = bisect(STONES, x)
    return bisect(STONES, y, low, len(STONES)) - low

LIMIT = 1500000

from math import log, ceil
from itertools import product

m_max, n_max = ceil(log(LIMIT, 2)), ceil(log(LIMIT, 3))
sb_primes = {2}

# generate candidates up to limit
for m, n in product(range(1, m_max), range(n_max)):
    cand = 2**m * 3**n + 1
    # check primality
    if cand < LIMIT and all(cand % x for x in range(3, int(cand**0.5)+1, 2)):
        sb_primes.add(cand)


def solve(x, y):
    return sum(x <= p < y for p in sb_primes)

M=[2,3,5,7,13,17,19,37,73,97,109,163,193,257,433,487,577,769,1153,1297,1459,2593,2917,3457,3889,10369,12289,17497,18433,39367,52489,65537,139969,147457,209953,331777,472393,629857,746497,786433,839809,995329,1179649,1492993]
solve=lambda L,R:sum(L<=V<R for V in M)

from math import*;solve=lambda x,y:len({2**m*3**n+1
for n in range(0,ceil(log(y-1,3)))
for m in range(ceil(log(max(~-x/3**n,1),2)),ceil(log(~-y/3**n,2)))
if all((2**m*3**n+1)%d for d in range(2,int((2**m*3**n+1)**.5)+1))})