# Tag Info

## Hot answers tagged number-theory

248

hello, world!, 13 hello, world!

163

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: . ? ' . . . . . ....

132

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) >...

121

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 ...

100

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 ...

71

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 ...

71

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 ...

69

Pyth, 4 bytes }QPQ Prints True or False.

64

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 + b)... 63 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. 49 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: ? \ . " > " ! * + { &... 49 Mathematica, 16 bytes CarmichaelLambda Well... 49 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 ... 48 Help, WarDoq!, 1 byte P Outputs 1 if the input is prime, 0 otherwise. 47 Jelly, 5 bytes ’&C²> Try it online! or verify all test cases. Let$\newcommand{\&}[]{\text{ & }}j$be a strictly positive integer.$j + 1$toggles all trailing set bits of$j$and the adjacent unset bit. For example,$10011_{2} + 1 = 10100_{2}$. Since${\sim}j = -(j + 1) = -j - 1$,$-j = {\sim}j + 1$, so$-n$applies the above ... 47 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$\newcommand{\&}[]{\text{ & }}j$be a strictly positive integer.$j + 1$toggles all trailing set bits of$j$and the adjacent unset bit. For example,$10011_{2} + 1 = 10100_{2}$. Since${\sim}j = -(j + 1) = -j - 1$,$-j =...

46

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) ...

46

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 ...

46

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.

44

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

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 ...

39

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 online. ...

38

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 ...

38

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?

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) ...

37

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, 11 bytes PartitionsP Explanation ¯\_(ツ)_/¯

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