Looking for shorter alternatives to `range(...)`

Question

The best solution I've found so far for a golf code puzzle I'm working on includes two rather fat-looking invocations of range. I'm very new at code golf, especially in Python, so I could use a few tips.

The relevant fragment is this

[x for x in range(n+1,7**6)if`x`==`x`[::-1]*all(x%i for i in range(2,x))]

The upper limit of the first range is not a sharp one. It should be at least 98690, and all else being equal (golf-wise, that is), the smaller the difference between this upper limit and 98690 the better, performance-wise¹. I'm using 7⁶ (=117649) because 7**6 is the shortest Python expression I can come up with that fits the bill.

In contrast, the lower limit in the first range, as well as both limits in the second one, are firm. IOW, the program (in its current form) will produce incorrect results if those limits are changed.

Is there a way to shorten one or both of the expressions

range(n+1,7**6)
range(2,x)

?

BTW, in this case, aliasing range to, say, r gains nothing:

r=range;rr
rangerange

EDIT: FWIW, the full program is this:

p=lambda n:[x for x in range(n+1,7**6)if`x`==`x`[::-1]*all(x%i for i in range(2,x))][0]

p(n) should be the smallest palindromic prime greater than n. Also, p should not be recursive. Warning: It is already obscenely slow!

---

_{¹Yes, I know: performance is irrelevant in code golf, but that's why I wrote "all else being equal (golf-wise, that is)". For example, my choice of 7**6, and not the more immediately obvious, but poorer-performing, "golf-equivalent" alternative 9**9. I like to actually run my code golf attempts, which means not letting the performance degrade to the point that it would take years to run the code. If I can help it, of course.}

Answer 1

Make it a single loop

As is, you have two loops: one iterating over x that might be palindromic primes, another iterating over i to check if x is prime by trial division. As you noticed, loops is Python take many characters, often to write range, but also to write while _: or for x in _. So, a golfed Python solution should take pains to use as few loops as possible.

feersum's comment "The best-golfed programs often make surprising connections between different part of the programs" is very applicable here. The prime-checking might seem like a separate subroutine for which all(x%i for i in range(2,x)) is the classic expression. But we'll do it another way.

The idea is to use Wilson's Theorem. For each potential prime k, we keep a running product of (k-1)!, and check is it's a multiple of k. We can keep track of (k-1)! while we test potential k to be prime palindromes by keeping a running product P.

Actually, we'll use the stronger version of Wilson's Theorem that (k-1)! % k equals 0 for composite k and only for composite numbers, except k=4 gives 2, and so (k-1)!**2 % k equals 0 exactly for composite numbers. We'll update P to equal k!**2 via the update P*=k*k.

(See this answer for this method used to find primes in Python.)

Putting it all together:

def p(n):
 k=P=1
 while(`k`!=`k`[::-1])+(k<=n)+(P%k==0):P*=k*k;k+=1
 return k

This isn't yet fully golfed -- the condition in particular is written inefficiently. We can compress the condition to check that k is a palindrome while at the time enforcing the other conditions via a chained inequality.

def p(n):
 k=P=1
 while`k`*(P%k>0>n-k)!=`k`[::-1]:P*=k*k;k+=1
 return k

Answer 2

AFAIK, not really.

Range is commonly used in python golfs because it is the shortest way to generate lists of increasing/decreasing numbers.

That said, it appears to be slightly (7 bytes) shorter to avoid using range and instead call a wrapped while loop:

def p(n):
    n+=1
    while`n`*all(n%i for i in range(2,n))!=`n`[::-1]:n+=1
    return n

Thanks to @xnor (as always) for improving the while condition's logic :)

Answer 3

When using iterative algorithms such as Newton method or calculating fractals, where you usually need to perform iterations without actually caring about the index you can save some characters by iterating over short strings instead.

for i in range(4):x=f(x)
for i in'asdf':x=f(x)

At seven iterations this breaks even with range. For more iterations use backtics and large numbers

for i in`9**9**5`:pass

This runs 56349 times which should be enough for all practical purposes. Playing around with numbers and operators lets you hardcode a wide range of numbers this way.