# Tag Info

## Hot answers tagged number-theory

224

hello, world!, 13 hello, world!

156

Hexagony, 29 bytes .?'.).@@/'/.!.>+=(<.!)}($>(<% The readable version of this code is: . ? ' . ) . @ @ / ' / . ! . > + = ( < . ! ) } ($ > ( < % . . . . . . . . Explanation: It test if there is a number from 2 to n-1 who divides n. Initialization: Write n in one memory cell and n-1 in an other: . ? ' . . . . . ....

118

C, 0.026119s (Mar 12 2016) #include <math.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define cache_size 16384 #define Phi_prec_max (47 * a) #define bit(k) (1ULL << ((k) & 63)) #define word(k) sieve[(k) >> 6] #define sbit(k) ((word(k >> 1) >...

110

ArnoldC, 299 283 bytes IT'S SHOWTIME HEY CHRISTMAS TREE i YOU SET US UP 0 GET YOUR ASS TO MARS i DO IT NOW I WANT TO ASK YOU A BUNCH OF QUESTIONS AND I WANT TO HAVE THEM ANSWERED IMMEDIATELY GET TO THE CHOPPER i HERE IS MY INVITATION i I LET HIM GO 2 ENOUGH TALK TALK TO THE HAND i YOU HAVE BEEN TERMINATED This outputs 1 (which is truthy) for odd input and ...

99

CJam - 13 q~,>{mfW=}$0= Try it at http://cjam.aditsu.net/ Example input: 2001 2014 Example output: 2002 Explanation: q~ reads and evaluates the input, pushing the 2 numbers on the stack (say min and max) , makes an array [0 1 ... max-1] > slices the array starting at min, resulting in [min ... max-1] {…}$ sorts the array using the block to ...

68

Hexagony, 218 92 58 55 bytes Notice: This answer has been solidly beaten with a side-length 4 solution by Etoplay. )}?}.=(..]=}='.}.}~./%*..&.=&{.<......=|>(<..}!=...&@\[ The first ever non-trivial (i.e. non-linear) Hexagony program! It is based on the same squared-factorial approach as Sp3000's Labyrinth answer. After starting out ...

66

Regex (.NET PCRE flavour), 183 129 bytes Don't try this at home! This is not really a contender for the win. But Eric Tressler suggested solving this problem with nothing but a regex, and I couldn't resist giving it a go. This might be is possible in PCRE as well (and even shorter, see below), but I chose .NET because my solution needs arbitrary-length ...

66

Pyth, 4 bytes }QPQ Prints True or False.

56

Python 2, 61 47 bytes lambda n:[k/n for k in range(n*n)if k/n*k%n==1] Try it online! Background Consider the ring $(Z_n, +_n, \cdot_n)$. While this ring is usually defined using residue classes modulo $n$, it can also be thought of as the set $Z_n = \{0, \dots, n - 1\}$, where the addition and multiplication operators are defined by \$a +_n b = (a +... 55 Retina, 16 bytes ^(?!(..+)\1+$).. Try it online! Let's start with a classic: detecting primes with a regex. Input should be given in unary, using any repeated printable character. The test suite includes a conversion from decimal to unary for convenience. A Retina program consisting of a single line treats that line as a regex and prints the number of ...

52

CJam, 4 bytes qimp CJam has a built-in operator for primality testing.

48

Binary lambda calculus, 114 bits = 14.25 bytes Hexdump: 00000000: 4457 42b0 2d88 1f9d 740e 5ed0 39ce 80 DWB.-...t.^.9.. Binary: 010001000101011101000010101100000010110110001000000111111001110101110100000011100101111011010000001110011100111010 Explanation 01 00 (λx. │ 01 00 ...

47

HTML+CSS, 254+nmax*28 bytes We can check primality using regular expressions. Mozilla has @document, which is defined as: @document [ <url> | url-prefix(<string>) | domain(<string>) | regexp(<string>) ]# { <group-rule-body> } To filter elements via CSS based on the current URL. This is a single pass, so we have to do two ...

47

Mathematica, 16 bytes CarmichaelLambda Well...

46

Python, 22 bytes lambda N:N-1&1-N>N**.5 This is a port of my Jelly answer. Test it on Ideone. How it works Let j be a strictly positive integer. j + 1 toggles all trailing set bits of j and the adjacent unset bit. For example, 100112 + 1 = 101002. Since ~j = -(j + 1) = -j - 1, -j = ~j + 1, so -n applies the above to the bitwise NOT of j (which ...

46

brainfuck, 8 bytes +[,>,]<. Input is in unary. Output is the 1 (truthy) for odd numbers and NUL (falsy) for even numbers. Try it online! How it works We start by incrementing the current cell with + to be able to enter the while loop [,>,]. In each iteration, , reads a byte from STDIN, > advances to the cell to the right, then , reads ...

45

Help, WarDoq!, 1 byte P Outputs 1 if the input is prime, 0 otherwise.

45

05AB1E, 2 bytes fP Try it online! How it works f Implicitly take input and compute the integer's unique prime factors. P Take the product.

43

Regex (.NET), 122 113 bytes ^(?=((?=.*$(?<=^(\3+(.+.))(.*?(?>(.\4)?)))).)+(.*))((?=.*(?=\6$)(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))).)+ Assuming input and output are in unary, and the output is taken from the main match of the regex. Breakdown of the regex: ^(?=((?=.*$(?<=^(\3+(.+.))(.*?(?>(.\4)?)))).)+(.*)) calculates π̅(x) ...

43

CJam, 18 17 13 bytes Thanks to aditsu for saving 4 bytes. qW:O%eu~"eo"= Try the test suite here. (The test suite is too long for the permalink. Just copy them from the challenge spec.) Explanation q e# Read the input. W:O e# Push a -1 and store it in variable O. % e# Use the -1 to reverse the string, because CJam's stack-based nature and the ...

40

Hexagony, 28 bytes Since Etoplay absolutely trounced me on this question, I felt that I had to outgolf his only other answer. ?\.">"!*+{&'=<\%(><.*.'(@>'/ Try it online! I use Wilson's Theorem, like Martin did in his answer: Given n, I output (n-1!)² mod n Here it the program unfolded: ? \ . " > " ! * + { & ' = < \ % ...

40

Haskell, 41 bytes i=((!!).).iterate i(($3).i(i1)(*3))4 64 Explanation: (i1)f n = i f 1 n computes the nth iterate of the function f starting at 1. In particular, (i1)(*3)n = 3^n, and iterating this construction m times gives i(i1)(*3)m n = u(3, n, m). We can rewrite that as (($n).i(i1)(*3))m = u(3, n, m), and iterate this construction k times ...

37

Jelly, 5 bytes ’&C²> Try it online! or verify all test cases. Background Let j be a strictly positive integer. j + 1 toggles all trailing set bits of j and the adjacent unset bit. For example, 100112 + 1 = 101002. Since ~j = -(j + 1) = -j - 1, -j = ~j + 1, so -n applies the above to the bitwise NOT of j (which toggles all bits), thus toggling all ...

37

20 languages Using  ()-#*.05;=>^Vefikloqrst (24 characters) so far: let f l=floor(l**0.5);; OCaml let f l=floor(l**0.5) F# f(l)=floor(l^.5) Julia f(o)=floor(o^.5) PARI/GP s^+>5 0>5 0*.5l Pyth (* **.5).floor Perl 6 floor.(**0.5) Haskell flr.(tt ^.5) ...

35

Retina, 16 ^(.+)\1* \1+1 This doesn't use Euclid's algorithm at all - instead it finds the GCD using regex matching groups. Try it online. - This example calculates GCD(8,12). Input as 2 space-separated integers. Note that the I/O is in unary. If that is not acceptable, then we can do this: Retina, 30 \d+ $* ^(.+)\1* \1+$ $1 1+$.& Try it ...

35

Z80 Assembly (8-bit), 2 bytes The following code only works with values up to 255: ; Input is given in register A. ; P flag is set if A is evil. B7 or A C9 ret 16-bit version (works on all test cases), 3 bytes This works with values up to 65535. ; Input is given in BC. ; Output is the same as above. 78 ld A,B A9 xor C C9 ret If you'...

34

Mathematica, 4 bytes OddQ Gives True for odd inputs and False for even inputs, who knew? There's also EvenQ, but who would want to type all of that?

34

Mathematica, 11 bytes PartitionsP Explanation ¯\_(ツ)_/¯

33

Mornington Crescent, 2448 bytes We're back in London! Take Northern Line to Bank Take Circle Line to Bank Take District Line to Parsons Green Take District Line to Bank Take Circle Line to Hammersmith Take District Line to Upney Take District Line to Hammersmith Take Circle Line to Victoria Take Victoria Line to Seven Sisters Take Victoria Line to Victoria ...

Only top voted, non community-wiki answers of a minimum length are eligible