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)

Source: codewars | Difficulty: EASY

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 = 1500000
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 ** 0.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}
for (m, n) in product(range(1, m_max), range(n_max)):
	cand = 2 ** m * 3 ** n + 1
	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) ** 0.5) + 1)))})