Highlighting prime numbers with CSS | Hacker News Reader

Highlighting prime numbers with CSS

github.com

97 pointsmholt21 comments

The highlighting and counting is cool but isn't this just colouring prime numbered elements (off by one) by knowing the primes up to √n? Bit of a circular problem! (:

It'd be pretty cool if CSS could define new rules based on counters and calculated properties. Then you might be able to bootstrap from something small like "2 is prime" and discover the rest of the primes up to n. Is this sort of wizardry possible?

I would doubt it's possible, considering the methods that we use to detect primes come down to brute force. It's hard to build an algorithm when we don't have a formal proof of how primes work/can be detected.

Well it's definitely possible unless I'm a moron (correct me if I am). If you have the primes up to √n you can find all primes up to n because everything else will be composite of the primes you know already. This is basically what TFA is doing. What I was suggesting is that it would be cool if you could avoid defining rules explicitly for (3n+6), (5n+10), etc and have them appear from some feedback loop where we go from a sequence of primes up to n, to n^2, to n^4...

CSS4, let's do it.

I don't know if CSS is Turing complete already, but I'm pretty sure it would have to be if it allowed you to implement something like that...

No, it would only need to be primitive recursive [0] because you can bound its runtime. There's actually a lot you can do without Turing completeness.

[0]: https://en.wikipedia.org/wiki/Primitive_recursive_function#C...

Pure CSS game: https://codepen.io/elad2412/pen/hBaqo

Rule110 (After setting first row requires alternation of tab/space to run): https://codepen.io/elrumordelaluz/pen/wqLyH?editors=010

stackoverflow discussion: https://stackoverflow.com/questions/2497146/is-css-turing-co...

Modern prime testing is quite far from brute force. Tests such as AKS[1], ECPP[2], and APR[3] can determine whether a number is prime in polynomial time (in the number of bits/digits), whereas a true brute force search would be exponential.

[1]https://en.wikipedia.org/wiki/AKS_primality_test

[2]https://en.wikipedia.org/wiki/Elliptic_curve_primality_provi...

[3]https://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%8...

You're right, I misspoke I should have been more precise and said that out way of finding primes isn't based on a specific theorem or algorithm in that we still have to take a number and demonstrate its primeness.

You can use the same trick dividing by all the numbers up to sqrt(n) [or n-1], instead of dividing by prime numbers.

You can replace

  li:first-child,
    li:nth-child(2n + 4),
    li:nth-child(3n + 6),
    li:nth-child(5n + 10),
    li:nth-child(7n + 14) {
      color: grey;
      counter-increment: nature-count nonprime-count;
    }

with

  li:first-child,
    li:nth-child(2n + 4),
    li:nth-child(3n + 6),
    li:nth-child(4n + 8),
    li:nth-child(5n + 10),
    li:nth-child(6n + 12),
    li:nth-child(7n + 14) 
    li:nth-child(8n + 16) 
    li:nth-child(9n + 18)
    li:nth-child(10n + 20) {
      color: grey;
      counter-increment: nature-count nonprime-count;
    }

So this is something I found interesting:

The number of rules is listed in the TFA as O(sqrt(n)/log(sqrt(n)), which is the same as O(sqrt(n)/log(n)), and slightly better than O(sqrt(n)), which is the number of rules needed if you have rules for the composites as well. That means that in this case, the constant factor is much more important than the complexity, in terms of how many rules we need.

nth-child()/nth-type-of() coupled with CSS variables and calc() plus some other CSS ingredient yet to be found should result in Turing completeness soon enough. Looking forward to 100% pure CSS sites in 2020.

> https://user-images.githubusercontent.com/2993947/28248599-d...

I see a pattern in this image. There are twelve columns, and most of the primes seem to occur in 4 of them.

What's the name of this?

The numbers in the other columns are multiples of 2 or 3, so you wouldn't expect to see any primes in those columns other than 2 and 3 themselves.

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

In base 12 those are just the columns for 1, 5, 7, and 11, the only numbers between 1 and 12 that aren't divisible by any of 12s factors. If you do this for any base the prime numbers will fall in columns like those.

Note that there aren't any prime numbers ending in 2 or 5 in base 10 (except 2 and 5), in base 12 it would be the same for numbers ending in 2, 3, 4, 6, 8, 9 and 10.

Math?

Primes will only appear in columns whose index is coprime with 12. That's because 12n+2 is divisible by 2. 12n+3 by 3, etc for 12n+4, 12n+6, 12n+8, 12n+9, 12n+10. (For n>0. that's why there are primes on the first line)

The unique prime factorisation of 12.

12 factors into 2, 2 and 3. If a column is index 2n or 3n it will never contain a prime after the first row. The columns that match that here are: 2, 3, 4, 6, 8, 10, 12. The columns that don't are 1, 5, 7, 11 - your four.

Not exactly what you are seeing but check this as well:

https://en.wikipedia.org/wiki/Ulam_spiral

I don't quite understand the reason to use Xn+2X, don't we just need a Sieve of Erastothenes (sp?): change the color of all multiples leaving all primes in the base colour?

That's what it does, but the counting starts from zero. So if we select 7 as a prime we get 7n. For n=0,1,2 we get 0,7,14, of which only 14 is the one we want to remove.

The highlighting I have seen before (maybe in some other form). But the counting used features of CSS new to me, very interesting.

Reply on news.ycombinator.com