ryl00•

Should have just used a regular expression

21
ProgramTheWorld•

Ironically the expression is not regular. It would be impressive if it is actually a regular expression which can be evaluated in linear time instead of an “enhanced” regular expression with backtracking.

14
flaghacker_•

Well regular expressions aren't powerful enough to only recognize primes.

8
julesjacobs•

They can however recognise numbers that are not divisible by a given finite set of numbers.

8
sim642•

Isn't primality testing with a closed form expression supposed to be impossible or something? Where's the catch?

Edit: Now looking closer at the expression it seems to do something weird: bitwise negates an arbitrary precision number in ~2**n. The power of two has only one bit set so it's complement should have all but one but these are arbitrary precision integers so that means infinitely many bits set. I wonder what's up with that, how does that work or what semantics it has.

16
harlows_monkeys•

Isn't primality testing with a closed form expression supposed to be impossible or something? Where's the catch?

Depends on exactly what you mean by closed form, but if the factorial function is allowed, then there is a simple closed form for test for primes: n > 1 is prime if and only if ((n-1)! + 1)/n is an integer. See Wilson's theorem.

10
killerstorm•

these are arbitrary precision integers so that means infinitely many bits set.

Arbitrary precision integers are usually modeled as an bit or octet string + length. Bitwise negation only flips bits which do exist.

It appears that python models them on bit level (i.e. bit length is specified), which makes sense for a high-level language.

So e.g.:

>>> ~2**63
-9223372036854775809L
>>> ~2**64
-18446744073709551617L
>>> ~2**65
-36893488147419103233L
3
sim642•

Bitwise negation only flips bits which do exist.

But that's implementation detail now. The same number may be represented with however many zeroes in front but the number of ones in the complement would vary then.

2
rrssh•

I'm not sure if that's the source of your confusion, but it's just an increment, -~x == x+1. The infinite bits are only there for half a moment.

2
sim642•

infinite bits are only there for half a moment

Yes, but that's not how computers work. the ~x is computed first anyway. It just happens to be negated afterwards, which in two's complement involves another bitwise negation (on infinitely many 1s now).

Edit: I looked further into it and found the following:

Integers (int) These represent numbers in an unlimited range, subject to available (virtual) memory only. For the purpose of shift and mask operations, a binary representation is assumed, and negative numbers are represented in a variant of 2’s complement which gives the illusion of an infinite string of sign bits extending to the left. (https://wiki.python.org/moin/BitManipulation#Python_Integers)

and

Of course, Python doesn't use 8-bit numbers. It USED to use however many bits were native to your machine, but since that was non-portable, it has recently switched to using an INFINITE number of bits. Thus the number -5 is treated by bitwise operators as if it were written "...1111111111111111111011". (https://wiki.python.org/moin/BitwiseOperators#line-22)

So it just uses additional trickery to make the number actually seem infinite w.r.t. bitwise operators.

7
crescentroon•

Yes, but that's not how computers work

As you've seen, the Python interpreter is so far abstracted from the hardware that a lot of low level assumptions simply are not valid.

It's an amazing feature that makes your life so much easier - until you need to optimise your code and then who knows what the interpreter is doing?

3
sim642•

It's rather weird though because bitwise operators are intentionally doing something very low level. Their semantics are defined in that low level. The Python bigint abstraction of them is actually blurring the lines of of making anything easier because suddenly the well known semantics make no sense.

1
rrssh•

https://math.stackexchange.com/a/9203

"Closed form" doesn't have a definition, or rather it depends on which functions you allow or disallow.

1
sim642•

Sure but in the context of the question it's very well-defined: arithmetic, bitwise and comparison operators.

7
[deleted]•

[deleted]

1
[deleted]•

[deleted]

0
sim642•

1007 ≠ 10007

2
Azuvector•

The comment on the proposed answer is hilariously accurate.

I have no idea what's going on here, but it's pretty darn cool. – Nit

2
aullik•

Can someone explain to me why they are still using python 2?

2†
rrssh•

For this challenge, literally one reason, saving a byte for each // (division).

18
sim642•

Probably no good reason, just requiring comparable answers although it doesn't make a real difference.

3
gnikdroy•

Can someone explain what the heck that was?

2
Aureliony•

What's the time complexity?

2
DanReach•

^ this guy's asking for a Big O

1
[deleted]•

[removed]

1
Edwinb60•

Check out this VERY USEFUL Smart Map in Python Tutorial series 2018. Blog https://ebisys.blogspot.com Youtube https://youtu.be/sBxCOEXkQuA

-5

Delete this trivial nonsense please.

-55
BroJobBiggs•

Username checks out. What a dickbag!

11

You think bill cosby did nothing wrong? He one of the most prolific serial rapists in history you sick fuck!

-11
BroJobBiggs•

The rape I could forgive. But ghost dad, that was just awful.

2
DanReach•

Why trivial?

9
stable_carbocation•

Username checks out.

4