title: Unicode UTF Converter

text:
# Question
Title: Unicode UTF Converter
The goal is to create a fully compliant converter between the official Unicode encodings as given in the UTF FAQ. Given that this is centred on Unicode, I will accept the answer with the lowest byte count using the best possible of the involved encodings (which will probably be UTF-8, unless maybe you program it in APL). I apologize for the long post, but a lot of it is explaining the encodings which can also be accessed in the official specification (pdf, section 3.9 D90 - D92), or Wikipedia.

# Specifications

*If at any time your language of choice cannot exactly meet a requirement, substitute it with something that sticks the spirit of the rules given. Eg. not every language has built-in arrays, functions etc.*

* No using string libraries/functions, or encoding libraries/functions. The point of this code golf is to implement the converter using bit/byte manipulation. Using strings themselves in their capacity as a character or byte array is allowed though. Oh, and no OS calls which perform the conversion either.
* The converter is a function which will take three parameters: a byte array representing the encoded input string, and the "input" and "output" encodings represented as numbers. Arbitrarily we will assign `UTF-8, UTF-16, UTF-16BE, UTF-16LE, UTF-32, UTF-32BE, and UTF32LE` numbers from 0 to 6 in that order. There is no need to check if the number is `< 0` or `> 6`, we will assume these parameters are correct. The converter will return a valid byte array in the desired output encoding.
* We will use the null character (`U+0000`) as a string terminator. Anything after this doesn't matter. We will assume that the input array has the null character somewhere so you do not need to do a bounds check.
* As per the FAQ, if the input byte array is invalid for its declared encoding, we must signal an error. We will do this in one of the following ways: crash the program, throw an exception, return null or return an array whose first four bytes are all 0 (so that it can be recognized as `U+0000` in every encoding).

# The Encodings

The official specifications must be followed, but Wikipedia provides a good (and as far as I believe correct) explanation of the encodings, and I will summarize them here for completeness. Note that UTF-16 and UTF-32 have variants for endianness.

## UTF-32, UTF-32LE, UTF-32BE

The simplest encoding, each code point is simply encoded in 4 bytes equal to its numeric value. LE/BE represents endianness (little endian/big endian).

## UTF-16, UTF-16LE, UTF-16BE

Code points from `U+0000 - U+FFFF` are encoded in 2 bytes equal to its numeric value. Larger values are encoded using a pair of *surrogates* which are reserved values from `U+D800 - U+DFFF`. So to encode points greater than `U+FFFF`, the following algorithm can be used (shamelessly copied from Wikipedia):

> * 0x010000 is subtracted from the code point, leaving a 20 bit number in the range 0..0x0FFFFF.
> * The top ten bits (a number in the range 0..0x03FF) are added to 0xD800 to give the first code unit or lead surrogate, which will be in the range 0xD800..0xDBFF \[...\].
> * The low ten bits (also in the range 0..0x03FF) are added to 0xDC00 to give the second code unit or trail surrogate, which will be in the range 0xDC00..0xDFFF \[...\].

## UTF-8

Code points from `U+0000 - U+007F` are encoded as 1 byte equal to its numeric value. From `U+0080 - U+07FF` they are encoded as `110xxxxx 10xxxxxx`, `U+0800 - U+FFFF` is `1110xxxx 10xxxxxx 10xxxxxx`, higher values are `11110xxx 10xxxxxx 10xxxxxx 10xxxxxx`. The `x`'s are the bits from the numeric value of the code point.

## BOM

The byte-order mark (BOM, `U+FEFF`) is used as the first code point to indicate endianness. Following the FAQ guidelines on BOMs, the BOM will be used as follows: For `UTF-8, UTF-16 and UTF-32` it is optional. If the BOM is absent in `UTF-16` or `UTF-32`, it is assumed to be big endian. The BOM **must not** appear in `UTF-16LE, UTF-16BE, UTF-32LE and UTF-32BE`.

# Common Pitfalls Causing Invalid UTF

Various things may cause a byte sequence to be invalid UTF.

* **UTF-8 and UTF-32:** Directly encoding surrogate code points ( `U+D800 - U+DFFF` ), or code points greater than `U+10FFFF`.
* **UTF-8:** Many invalid byte sequences.
* **UTF-16:** Unpaired, or improperly paired surrogates.
* **BOM:** Must be used as specified in the encoding section. Note that when outputting `UTF-16` or `UTF-32` (no inherent endianness specified) you can pick, but with little endian, you **must** include the BOM.

Note that non-characters and unassigned code points (both distinct from surrogates) are to be treated like regular characters.

# Answer
> 3 votes
# C++, (UTF-8) 971 bytes

```
#include<cstdint>
using u=uint8_t;using U=uint32_t;U i,o,x,b,m;U R(u*&p){x=*p++;if(!i){m=0;while(128>>m&x)++m;if(m>1)for(x&=127>>m;--m;)x=x<<6|((*p&192)-128?~0:*p++&63);return m?x=~0:x;}else if(i<3){x<<=8;x+=*p++;}else if(i<4){x+=*p++<<8;}else if(i<6){x<<=24;x+=*p++<<16;x+=*p++<<8;x+=*p++;}else{x+=*p++<<8;x+=*p++<<16;x+=*p++<<24;}return x;}U r(u*&p){U x0=R(p);if(i&&i<4&&x>>10==54)x=R(p)>>10==55?(x0<<10)+x-56613888:~0;if(!b++){if(x==65279)if(!i||i%3==1)r(p);else x=~0;else if(x==65534&&i==1)i=3,r(p);else if(x==4294836224&&i==4)i=6,r(p);}return x>1114111||x>>11==27?x=~0:x;}void w(U x,u*&p){if(!o){if(x<128)*p++=x;else{for(m=0;~63<<m&x;m+=6);for(*p++=~127>>m/6|x>>m;m;)*p++=128|x>>(m-=6)&63;}}else if(o<4&&x>65535)x-=65536,w(55296|x>>10,p),w(56320|x&1023,p);else if(o<3)*p++=x>>8,*p++=x;else if(o<4)*p++=x,*p++=x>>8;else if(o<6)*p++=x>>24,*p++=x>>16,*p++=x>>8,*p++=x;else*p++=x,*p++=x>>8,*p++=x>>16,*p++=x>>24;}int t(u*&p,u*&q){for(b=0,x=1;U(x+x);)w(r(p),q);return x;}

```

The readable program below can be condensed to the above form by filtering it through the following Perl command:

```
perl -p0 -e 's!//.*!!g;s/\s+/ /g;s/ \B|\B //g;s/0x[\da-f]+/hex($&)/ige;s/#include<[^<>]+>/\n$&\n/g;s/^\n+//mg'

```

The above command

* removes comments
* removes unnecessary whitespace
* converts hexadecimal literals to decimal
* reinstates newlines around `#include` lines

### Readable code

```
#include <cstdint>
using u = uint8_t;
using U = uint32_t;

U   i,                          // input encoding
    o,                          // output encoding
    x,                          // last read value
    b,                          // char count(BOM only valid when b==0)
    m;                          // temporary variable for measuring UTF-8

//   Encodings:
// 0 UTF-8
// 1 UTF-16
// 2 UTF-16BE
// 3 UTF-16LE
// 4 UTF-32
// 5 UTF-32BE
// 6 UTF-32LE

// Read a character or UTF-16 surrogate
U R(u*& p) {
    x = *p++;
    if (!i) { // UTF-8
        m=0; while (128>>m&x) ++m; // how many bytes?
        if (m>1) for (x&=127>>m; --m; ) x = x<<6 | ((*p&192)-128?~0:*p++&63);
        return m ? x=~0 : x;
    } else if (i<3) { // UTF-16, UTF-16BE
        x<<=8; x+=*p++;
    } else if (i<4) { // UTF-16LE
        x+=*p++<<8;
    } else if (i<6) { // UTF-32, UTF-32BE
        x<<=24; x+=*p++<<16; x+=*p++<<8; x+=*p++;
    } else { // UTF-32LE
        x+=*p++<<8; x+=*p++<<16; x+=*p++<<24;
    }
    return x;
}

// Read a character, combining surrogates, processing BOM, and checking range
U r(u*& p) {
    U x0 = R(p);
    if (i && i<4 && x>>10==54)
        x = R(p)>>10==55 ? (x0<<10)+x-56613888: ~0; // 56613888 == 0xd800<<10 + 0xdc00 - 0x10000
    if (!b++) {                 // first char - is it BOM?
        if (x==0xFEFF)
            if (!i || i%3==1)
                r(p); // BOM in UTF-8 or UTF-16 or UTF-32 - ignore, and read next char
            else
                x = ~0; // not allowed in these modes
        else if (x==0xFFFE && i==1)
            i=3,r(p); // reversed BOM in UTF-16 - change to little-endian, and read next char
        else if (x==0xFFFE0000 && i==4)
            i=6,r(p); // reversed BOM in UTF-32 - change to little-endian, and read next char
    }
    return x>0x10ffff || x>>11==27 ? x=~0 : x;
}

// Write character(assumed in-range)
void w(U x, u*& p) {
    if (!o) { // UTF-8
        if (x<128) *p++=x;        // ASCII
        else {
            for (m=0; ~63<<m&x; m+=6); // how many bits?
            for (*p++=~127>>m/6|x>>m; m; ) *p++ = 128|x>>(m-=6)&63;
        }
    } else if (o<4 && x>65535)  // UTF-16 surrogate
        x-=65536, w(0xD800|x>>10,p), w(0xDC00|x&0x3FF,p);
    else if (o<3)  // UTF-16, UTF-16BE
        *p++=x>>8, *p++=x;
    else if (o<4)  // UTF-16LE
        *p++=x, *p++=x>>8;
    else if (o<6)  // UTF-32, UTF-32BE
        *p++=x>>24, *p++=x>>16, *p++=x>>8, *p++=x;
    else  // UTF-32LE
        *p++=x, *p++=x>>8, *p++=x>>16, *p++=x>>24;
}

// Transcode
int t(u*& p, u*& q)                  // input, output
{
    for (b=0,x=1;U(x+x);)    // exit condition is true only for x==-x, i.e. 0 and ~0
        w(r(p),q);
    return x;
}

```

The function to be called is `t()`, with input and output encodings passed in the global variables `i` and `o` respectively, and `p` pointing at the bytes of input, which **must** be null-terminated. `q` points to the output buffer, which will be overwritten, and **must** be big enough for the result - there is no attempt to avoid buffer overrun.

I hope the code comments are sufficiently explanatory - ask below if one of them is too cryptic (but do make an effort first!).

I compiled a substantial test suite whilst developing this answer; I include it below for the benefit of other entrants, and to document my interpretation of requirements:

### Test functions

```
#include <vector>
#include <iostream>

std::ostream& operator<<(std::ostream& out, const std::vector<u>& v)
{
    out << "{ ";
    for (int i: v) out << i << " ";
    out << "}";
    return out;
}

int test_read(int encoding, std::vector<u> input, U expected)
{
    b = 0;
    i = encoding;
    auto d = input.data();
    U actual = r(d);
    if (actual == expected) return 0;
    std::cerr << std::hex << "Decoding " << encoding << "; " << input << " gave " << actual
              << " instead of " << expected << std::endl;
    return 1;
}

int test_write(int encoding, U input, std::vector<u> expected)
{
    o = encoding;
    u buf[20], *p = buf;
    w(input, p);
    std::vector<u> actual(buf,p);
    if (expected == actual) return 0;
    std::cerr << std::hex << "Encoding " << encoding << "; " << input << " gave " << actual
              << " instead of " << expected << std::endl;
    return 1;
}

int test_transcode(int ienc, std::vector<u> input, int oenc, std::vector<u> expected)
{
    b = 0;
    i = ienc; o = oenc;
    u buf[200], *p = buf, *d = input.data();
    int result = t(d, p);
    std::vector<u> actual(buf,p);
    if (result ? expected.empty() : expected == actual) return 0;
    std::cerr << std::hex << "Encoding " << ienc << " to " << oenc << "; " << input << " gave " << actual
              << " instead of " << expected << std::endl;
    return 1;
}

```

### Test suite

```
static const U FAIL = ~0;
int main() {
    int e = 0;                        // error count
    // UTF-8
    e += test_read(0, { 128 }, FAIL); // unexpected continuation
    e += test_read(0, { 128, 1 }, FAIL);
    e += test_read(0, { 128, 128 }, FAIL);
    e += test_read(0, { 192, 192 }, FAIL); // start without continuation
    e += test_read(0, { 192, 0 }, FAIL);
    e += test_read(0, { 224, 0 }, FAIL);
    e += test_read(0, { 224, 192 }, FAIL);
    e += test_read(0, { 0xf4, 0x90, 128, 128 }, FAIL); // Unicode maximum+1

    e += test_read(0, { 127 }, 127);
    e += test_read(0, { 192, 129 }, 1); // We accept overlong UTF-8
    e += test_read(0, { 0xc2, 128 }, 128);
    e += test_read(0, { 224, 128, 129 }, 1);
    e += test_read(0, { 0xef, 128, 128 }, 0xF000);
    e += test_read(0, { 0xef, 191, 191 }, 0xFFFF);
    e += test_read(0, { 0xf4, 128, 128, 128 }, 0x100000);
    e += test_read(0, { 0xf4, 0x8f, 191, 191 }, 0x10FFFF); // Unicode maximum

    e += test_read(0, { 0xEF, 0xBB, 0xBF, 127 }, 127); // byte-order mark

    e += test_write(0, 0, { 0 });
    e += test_write(0, 127, { 127 });
    e += test_write(0, 128, { 0xc2, 128 });
    e += test_write(0, 255, { 0xc3, 191 });
    e += test_write(0, 0xFFFF, { 0xef, 191, 191 });
    e += test_write(0, 0x10FFFF, { 0xf4, 0x8f, 191, 191 });

    // UTF-16
    e += test_read(1, { 0, 1 }, 1);
    e += test_read(1, { 0xd8, 0, 0xdc, 1 }, 0x10001);
    e += test_read(1, { 0xdb, 0xff, 0xdf, 0xff }, 0x10ffff);

    e += test_read(1, { 0xd8, 0, 0xd8, 1 }, FAIL); // mismatched surrogate
    e += test_read(1, { 0xd8, 0, 0, 1 }, FAIL); // mismatched surrogate
    e += test_read(1, { 0xdc, 0 }, FAIL);

    e += test_write(1, 1, { 0, 1 });
    e += test_write(1, 256, { 1, 0 });
    e += test_write(1, 0xffff, { 255, 255 });
    e += test_write(1, 0x10001, { 0xd8, 0, 0xdc, 1 });
    e += test_write(1, 0x10ffff, { 0xdb, 0xff, 0xdf, 0xff });

    // UTF-16LE
    e += test_write(3, 1, { 1, 0 });
    e += test_write(3, 256, { 0, 1 });
    e += test_write(3, 0x10001, { 0, 0xd8, 1, 0xdc });
    e += test_write(3, 0x10fffe, { 0xff, 0xdb, 0xfe, 0xdf });

    // UTF-16 byte-order mark
    e += test_read(1, { 0xFE, 0xFF, 0x0, 1 }, 1); // byte-order mark
    e += test_read(1, { 0xFF, 0xFE, 1, 0x0 }, 1); // reversed byte-order mark
    // disallowed byte-order marks
    e += test_read(2, { 0xFE, 0xFF }, FAIL);
    e += test_read(3, { 0xFF, 0xFE }, FAIL);
    // reversed byte-order mark is an unassigned character - to be treated like regular character, according to question
    e += test_read(2, { 0xFF, 0xFE }, 0xfffe);
    e += test_read(3, { 0xFE, 0xFF }, 0xfffe);

    // UTF-32
    e += test_read(4, { 0, 0, 0, 1 }, 1);
    e += test_read(4, { 1, 0, 0, 0 }, FAIL);
    e += test_write(4, 1, { 0, 0, 0, 1 });
    e += test_write(4, 0x10203, { 0, 1, 2, 3 });

    // UTF-32LE
    e += test_read(6, { 0, 0, 0, 1 }, FAIL);
    e += test_read(6, { 1, 0, 0, 0 }, 1);

    // UTF-32 byte-order mark
    e += test_read(4, { 0, 0, 0xFE, 0xFF,  0, 0, 0, 1 }, 1); // byte-order mark
    e += test_read(4, { 0xFF, 0xFE, 0, 0,  1, 0, 0, 0 }, 1); // reversed byte-order mark
    // disallowed byte-order marks
    e += test_read(5, { 0, 0, 0xFE, 0xFF }, FAIL);
    e += test_read(5, { 0xFF, 0xFE, 0, 0 }, FAIL);
    e += test_read(6, { 0, 0, 0xFE, 0xFF }, FAIL);
    e += test_read(6, { 0xFF, 0xFE, 0, 0 }, FAIL);

    e += test_transcode(1, { 1, 2, 0xFE, 0xFF, 0, 0 }, // That's not a BOM; it's a zwnj when not the first char
                        1, { 1, 2, 0xFE, 0xFF, 0, 0 });
    e += test_transcode(1, { 0xFF, 0xFE, 1, 2, 0, 0 }, // reversed byte-order mark implies little-endian
                        1, { 2, 1, 0, 0 });
    e += test_transcode(4, { 0xFF, 0xFE, 0, 0, 1, 2, 0, 0, 0, 0 }, // reversed BOM means little-endian
                        4, { 0, 0, 2, 1, 0, 0, 0, 0 });
    e += test_transcode(1, { 0xdb, 0xff, 0xdf, 0xff, 0, 0 }, // U+10ffff UTF-16 to UTF-8
                        0, { 0xf4, 0x8f, 191, 191, 0 });

    return e;
}

```

# Answer
> 5 votes
# Python - 1367 UTF-8 chars

Alright! This was an extremely difficult question because of the sheer amount of work it took to understand and implement all the specifications, but I think that I have a correct implementation.

```
O,P,Q,R=65536,128,b'\xff\xfe\x00\x00',63
def A(x,y):assert x;return y
def B(x):
    o,c=[],0
    for b in x:
        if c:c,v=c-1,A(127<b<192,v<<6)|(b-P)
        else:
            c,v=(b>127)+(b>223)+(b>239),b
            if b>127:v=A(191<b<248,b&(R>>c))
        o+=[v][c:]
    return o[o[0]in(65279,O-2):]
def C(k):
    def o(x,s=None):
        for a,b in zip(x[k::2],x[1-k::2]):
            d=a|(b<<8)
            if s!=None:yield(A(56319<d<57344,d-56320)|(s<<10))+O;s=None
            elif 55295<d<57344:s=A(s<1024,d-55296)
            else:yield d
    return o
def D(x):n=(2,3,1)[[Q[:2],Q[1::-1],x[:2]].index(x[:2])];return C(n&1)(x[n&2:])
E=lambda a,b,c,d:lambda x:[L|(l<<8)|(m<<16) for L,l,m in zip(x[a::4],x[b::4],x[c::4])]
def F(x):n,m=((1,4),(-1,4),(-1,0))[[Q,Q[::-1],x[:4]].index(x[:4])];return E(*range(4)[::n])(x[m:])
S=lambda x,s=0,a=255:(x>>s)&a
G=lambda e:(e,)if e<P else(192|S(e,6),P|(e&R))if e<2048 else(224|S(e,12),P|S(e,6,R),P|(e&R))if e<O else(240|S(e,18),P|S(e,12,R),P|S(e,6,R),P|(e&R))
H=lambda e:(S(e,8),S(e))if e<O else(216|S(e-O,18),S(e-O,10),220+S((e-O)&1023,8),S(e-O))
I=lambda e:(S(e),S(e,8))if e<O else(S(e-O,10),216|S(e-O,18),S(e-O),220+S((e-O)&1023,8))
J=lambda e:(S(e,24),S(e,16),S(e,8),S(e))
K=lambda e:(S(e),S(e,8),S(e,16),S(e,24))
convert=lambda d,i,o:bytes(sum(map(L[o],N(list(M[i](d)))),()))if d else d
L,M=[G,H,H,I,J,J,K],[B,D,C(1),C(0),F,E(3,2,1,0),E(0,1,2,3)]
N=lambda d:[A(-1<x<1114112 and x&~2047!=55296,x)for x in d]

```

`convert` is the function that takes the data 'bytes' object, the input ID, and the output ID. It seems to work - although python seems to have a slightly broken usage of BOMs when unspecified in the encoding, so using python's builtin encoding to test modes 1 and 4 won't work.

Fun fact: The size is also 55516 or 101010101012.

773 chars for decoding, 452 for encoding, 59 for verification and 83 for miscellaneous parts.

# Answer
> 5 votes
## Python 3, 1138 bytes (UTF-8)

So it turns out that 14 hours of international travel is a *fantastic* opportunity to finish off a golfing challenge...

The conversion function is `C()`. This calls `u()`, `v()`, and `w()` to decode, and `U()`, `V()`, and `W()` to encode, UTF-8, -16 and -32, respectively. None of the encoders will output a BOM, but all of the decoders will correctly handle one. Error conditions result in an exception (usually a `ZeroDivisionError`, courtesy of the "die-suddenly" function `E()`).

```
from struct import*
l=len
j=''.join
b=lambda c:[*bin(c)[2:]]
P,Q,i,o,z,Z='HI10><'
B=65279
O,F,H,L,X=1024,65536,55296,56320,57344
E=lambda:1/0
R=lambda y,e,c,n:unpack(([[z,Z][y[:n]==pack(Z+c,B)],e][l(e)])+c*(l(y)//n),y)
S=lambda d,e:B!=d[0]and d or e and E()or d[1:]
def u(y,d=(),p=0):
 while p<l(y):
  q=b(y[p])
  if l(q)>7:
   x=q.index(o);C=1<x<5and q[x+1:]or E();X=x+p;X>l(y)>E();p+=1
   while p<X:q=b(y[p]);C=l(q)>7and(i,o==q[:2])and(*C,*q[2:])or E();p+=1
   d=*d,int(j(C),2)
  else:d=*d,y[p];p+=1
 return S(d,0)
def T(p):
 q=b(p);C=()
 while l(q)not in(7,11,16,21):q=o,*q
 while l(q)>6:C=int(i+o+j(q[-6:]),2),*C;q=q[:-6]
 return bytes(p<128and[p]or[int(i*(7-l(q))+o+j(q),2),*C])
U=lambda c:b''.join(map(T,c))
def v(y,e=''):
 c=R(y,e,P,2);d=[];n=0
 while n<l(c)-1:h,a=c[n:n+2];D=[(h,a),(F+(h-H)*O+a-L,)][H<=h<L<=a<X];M=3-l(D);n+=M;d+=D[:M]
 if n<l(c):d=*d,c[n]
 return S(d,e)
V=lambda c,e=z:W(sum(map(lambda p:([H+(p-F)//O,L+(p-F)%O],[p])[p<F],c),[]),e,P)
w=lambda y,e='':S(R(y,e,Q,4),e)
W=lambda c,e=z,C=Q:pack(e+C*l(c),*c)
K=(u,U),(v,V),(v,V,z),(v,V,Z),(w,W),(w,W,z),(w,W,Z)
def C(y,f,t):f,_,*a=K[f];_,t,*b=K[t];return t(f(y,*a),*b)

```

# Answer
> 2 votes
This ***ENTIRELY*** self-contained and `POSIX-compliant` `awk` function of my own making, that is

* fully-encapsulated with zero external dependencies
* can now encode any single Unicode code-point, in both `UTF-8` and `UTF-32 (BE+LE)`, plus any arbitrary byte, regardless of locale-setting (as long as it's not something like `EBCDIC`). The only part missing is `UTF-16`.
* is proven working on `mawk-1/2`, `gawk (in any mode other than -t)`, even `nawk (sans "\0" NUL byte)`, and
* doesn't need loops, recursion, pre-made lookups in any shape or form, or caching/memoization

***Every single*** threshold, range cutoff, scaling factor, and necessary offset (like `xC0 xE0 xF0` etc), both for the auto-detection part and the encoding part, are being dynamically generated on the fly, while requiring only 1 additional temp variable on top of the 2 needed for user inputs anyway.

My own benchmarking of `mawk-2` running it puts it within just 1.7x speed ratio against the built-in encoder in `gawk ( 1.0x )`, which is a decent showing for a user-level function benchmarked against compiled C-code binaries.

* `__` is code-point integer input, with auto-detection for out-of-range values such as `x < 0`, `1114111 < x`, plus the `UTF-16 surrogate ranges`, which would simply print out 1 single arbitrary byte that is its modulo-equivalent.
* `_` is optional - enter `-32` for `UTF32-LE` or `32` for `UTF32-BE`;

any other non-empty input, e.g. `"1"` or `"/"` or `"\t"` etc, forces it to use the `awk`-built-in `sprintf("%c", x)` single-character encoder, taking the input **as-is**, and printing out 1 character that will be locale-setting specific

(this feature is most useful when validating against `gawk` in unicode mode)

.

```
jot 1114112 0 | mawk 'BEGIN {  }

function chrUC8(__,_,___) {
    return \
    ((___=_)*_)>=(_+=_+=_^=_<_)^_ \
    ? ( (+___<-___)==(___=(--_+_)^_*(_^=++_))^!_ \
        ? sprintf("%c%c%c%c", (__=int(__) % (_*_*_*_))%_+___,
            int(__/_)%_+___, (__=int(__/_/_))%_+___, int(__/_)+___)\
        : sprintf("%c%c%c%c",  int((__%=_*_*_*_)/_/_/_)+___,
            int(__/_/_)%_+___, int(__/_)%_+___,__%_+___)\
                                 ) \
                                 :  +___  ||
          (((__=+__)+__)<_^_ && -__<=+__) ||
      ((___=(--_+_)^_*++_^_)<=__ && __<(_^_*(_+_)+___)) ||
                                  +__<-__ ||
                              ((_+_)^_*(_*_+_^_))<=__\
        ? sprintf("%c",+___<_?__: (__%(_^=_)+_)%_+___)\
    : (__+__)<(_+_)^_                                  \
        ? sprintf("%c%c", (___+=(_*=_*_)+_) +_+ int(__/_), __%_+___) \
    : __<_^(_+_)                                                    \
        ? sprintf("%c%c%c", _*(_+_) + (___+=(_*=_*_)+_) +_+ int(__/_/_),
                                     int(__/_)%_ + ___, __%_ + ___) \
        : sprintf("%c%c%c%c", _*-_+ (___+=(_*=_*_)+_) +_+_+ int(__/_/_/_),
                int(__/_/_)%_ +___, int(__/_)%_ + ___,__%_+___)
}'

```

The squeezed form is roughly **789 bytes**, give or take.

How can this form save space at all ?

> e.g. one can write 6 `ASCII`-bytes of `262144` or `2^18` or even `64^3` to scale 3 continuation bytes in the supplementary planes…

> …… or save space via `8^6` or `4^9`.

because truth be told, the number ***4***, and combinations of it, is all you need to encode everything about Unicode :

```
4
16
256
 #
128
 2048
   65536
      1114112
           ##
           64
           4096
             262144
                 ###
                  128
                   192
                    224
                     240
                      #####
                         1048576
                              2048
                                55296
                                   1024
                                     56320
                                        57344
      # gawk profile,
     created Thu Nov 10 14:26:19 2022

     gawk 'BEGIN {
     1     OFS="\f\b\b"
     1     print "",
     _=4,
     _*_,
     _^_,
     "#",
     _*(_+_)*_,
     _^_*(_+_),
     _^(_+_),
     (_+_)^_*(_^_+_*_),
     "##",
     _*_*_,
     (_+_)^_,
     _^(_+_)*_,
     "###",
     _*(_+_)*_,
     _^_-_*_*_,
     _^_-(_+_)*_,
     _^_-_*_,
     "#####",
     _*_^(_+_)*_,
     _^_*(_+_),
     _^_*(_^_-_-(_+_)*_-_),
     _^_*_,
     _^_*(_^_-(_+_)*_-_),
     (_^_-_*_-_*_)*_^_
}'

```

---
Tags: code-golf, unicode
---


title: Traverse a rectangle's antidiagonals

text:
# Question
Title: Traverse a rectangle's antidiagonals
There exists a bijection between the natural and rational numbers that works (approximately) like this:

1. You create a 1-indexed 2-dimensional grid.
2. In every field of this grid with position `(x, y)`, put the number `x / y`.
3. You start at `(1,1)` and iterate over the field in the following way:

However, this task is not about outputting rational numbers, but about following this pattern in a finite rectangle. This algorithm is best described by an image, but can also be described using words (0-indexing is used this time):

1. Start at `(0,0)`.
2. Go one field down, if in bounds, else right.
3. Go one field to the right and one up (in one step), if in bounds, else go to step 5.
4. Repeat step 3.
5. Go one field to the right, if in bounds, else down.
6. Go one field to the left and one down (in one step), if in bounds, else go to step 2.
7. Repeat step 6 until you reach an edge.
8. Go to step 2.

If at any point you encounter the bottom right field, stop.

## Task

Given a rectangle defined by two positive integers `w` and `h` (for **w**idth and **h**eight), output all points `(x, y)` on the rectangle in the order in which the above algorithm visits them.

* You must handle the possibility of `w` and `h` being equal to zero.
* The points can be 1- or 0-indexed.
* The first step must be downwards, not right.
* You can use any ordered sequence format as the return value.
* The length of the output sequence must always be `w * h`.
* The first and last element will always be `(0,0)` (or `(1,1)` one-indexed) and `(w-1, h-1)` (or `(w,h)`), respectively.
* Standard input / output rules apply.
* Standard loopholes are forbidden.

## Example 1

`w = 5`, `h = 3`

In this case, you should thus output:

```
0,0 0,1 1,0 2,0 1,1 0,2 1,2 2,1 3,0 4,0 3,1 2,2 3,2 4,1 4,2

```

## Example 2

`w = 4`, `h = 7`

Following the red line, the expected output is:

```
0,0 0,1 1,0 2,0 1,1 0,2 0,3 1,2 2,1 3,0 3,1 2,2 1,3 0,4 0,5 1,4 2,3 3,2 3,3 2,4 1,5 0,6 1,6 2,5 3,4 3,5 2,6 3,6

```

## Test cases (zero-indexed)

| Input | Output |
| --- | --- |
| `w=0`, `h=0` | `[]` |
| `w=0`, `h=123` | `[]` |
| `w=123`, `h=0` | `[]` |
| `w=1`, `h=1` | `[(0,0)]` |
| `w=2`, `h=2` | `[(0,0), (0,1), (1,0), (1,1)]` |
| `w=10`, `h=1` | `[(0,0), (1,0), (2,0), (3,0), (4,0), (5,0), (6,0), (7,0), (8,0), (9,0)]` |
| `w=1`, `h=10` | `[(0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (0,6), (0,7), (0,8), (0,9)]` |
| `w=3`, `h=3` | `[(0,0), (0,1), (1,0), (2,0), (1,1), (0,2), (1,2), (2,1), (2,2)]` |
| `w=4`, `h=4` | `[(0,0), (0,1), (1,0), (2,0), (1,1), (0,2), (0,3), (1,2), (2,1), (3,0), (3,1), (2,2), (1,3), (2,3), (3,2), (3,3)]` |
| `w=4`, `h=7` | `[(0,0), (0,1), (1,0), (2,0), (1,1), (0,2), (0,3), (1,2), (2,1), (3,0), (3,1), (2,2), (1,3), (0,4), (0,5), (1,4), (2,3), (3,2), (3,3), (2,4), (1,5), (0,6), (1,6), (2,5), (3,4), (3,5), (2,6), (3,6)]` |
| `w=5`, `h=3` | `[(0,0), (0,1), (1,0), (2,0), (1,1), (0,2), (1,2), (2,1), (3,0), (4,0), (3,1), (2,2), (3,2), (4,1), (4,2)]` |

This is , so the shortest output (measured in bytes) wins.

# Answer
# Jelly, 7 bytes

```
pS;ị¥$Þ

```

A dyadic Link that accepts \\$w\\$ on the left and \\$h\\$ on the right and yields the path as a list of 1-indexed coordinates.

**Try it online!** Or see the test-suite (converts the output to 0-indexing).

### How?

Each anti-diagonal consists of the maximal subset of coordinates that have the same sum. The path traverses these anti-diagonals in this coordinate-sum order. Those with odd sums are traversed in row order, while those with even sums are traversed in column order. (This is all true regardless of whether 0 or 1 indexing is employed.)

```
pS;ị¥$Þ - Link: integer, w; integer h
p       - ([1..w]) Cartesian product ([1..h]) -> coordinates
      Þ - sort by:
     $  -   last two links as a monad - f([r, c]):
 S      -     sum ([r, c]) -> r+c = #diagonal
    ¥   -     last two links as a dyad -f (#diagonal, [r, c]):
   ị    -       (#diagonal) index into ([r, c]) - 1-based and modular
                  -> r if #diagonal is odd; c otherwise
  ;     -       (#diagonal) concatenate (that)

```
> 6 votes

# Answer
# , 18 15 bytes

```
#:&;<@|.`</.@i.

```

Try it online!

Very similar to Gareth's answer in Zigzagify a matrix. This is the standard J approach for these types of problems, and all I do here is combine it with self-indexing.

Consider `3 3`:

* `i.` Create the matrix:

```
0 1 2
3 4 5
6 7 8

```
* `<@|.`</.` For each diagonal, alternate reverse-and-box and box. This is the heart of the logic:

```
┌─┬───┬─────┬───┬─┐
│0│1 3│6 4 2│5 7│8│
└─┴───┴─────┴───┴─┘

```
* `#:&;` Unbox and convert each number to mixed-base `3 3` -- this gives each number's self-index within the original matrix:

```
0 0
0 1
1 0
2 0
1 1
0 2
1 2
2 1
2 2

```
> 12 votes

# Answer
# Haskell, 65 bytes

```
w#h=[[n-m,m]|n<-[0..w+h],m<-cycle[id,(n-)]!!n<$>[0..n],n-m<w,m<h]

```

Attempt This Online!
> 6 votes

# Answer
# JavaScript (V8), 73 bytes

Expects `(w)(h)`. Prints the coordinates.

```
w=>h=>{for(i=j=0;~j||(j=++i)<w+h;j--)i-(x=i&1?i-j:j)<h&x<w&&print(x,i-x)}

```

Try it online!

### How?

We walk through the upper-left diagonals of a square of width \\$w+h\\$, going alternately from top-right to bottom-left and the other way around. We print only the coordinates that are within the target rectangle.

Below is an example for \\$w=3\\$ and \\$h=2\\$:

**NB**: Processing the longest diagonal never brings any new cell. It's just golfier to include it.
> 4 votes

# Answer
# Ruby, ~~66 64~~ 61 bytes

```
->w,h{[*1..w].product([*1..h]).sort_by{|a|[q=a.sum,a[~q%2]]}}

```

Try it online!

### How it works:

First, create the set of coordinates from the cartesian product of X and Y, then sort by sum and then by ascending or descending X alternatively.
> 4 votes

# Answer
# sclin, 46 bytes

```
O>a Q*"_`"map"+/"group""sort"rev2% \_` &#"mapf

```

Try it here! Takes input as list `[ h w ]`.

For testing purposes:

```
[3 5] ; \>A map f>o
O>a Q*"_`"map"+/"group""sort"rev2% \_` &#"mapf

```

## Explanation

Prettified code:

```
O>a Q* \_` map \+/ group () sort ( rev 2% \_` &# ) mapf

```

Assuming input \[ *h* *w* \].

* `O>a` vectorized range over \[ *h* *w* \]
* `Q* \_` map` Cartesian product and reverse each generated pair to get properly ordered matrix coordinates
* `\+/ group () sort` group pairs by sum and sort by sum
    + this creates a nicely ordered set of diagonals
* `( rev 2% \_` &# ) mapf` reverse every odd (0-indexed) diagonal and flatten into a list of pairs
> 3 votes

# Answer
# Alchemist, 145 bytes

```
_->In_r+In_d+s
s+r+d->z
z+0m->z+m+Out_l+Out_","+Out_u+Out_"\n"
0b+m+l+d->r+u
0b+m+0l+d->b+u
0b+m+r+0d->b+l
b+m+r+u->b+l+d
b+m+r+0u->l
b+m+0r+d->u

```

Try it online!

After the first two iterations, the atoms are a direct representation of the current state of the traversal.

`_`: starting atom

`s`: needed to initialize `r` and `d` properly

`z`: initialization complete

`u`, `d`, `l`, `r`: number of tiles away from top/bottom/left/right boundary

`m`: should move next iteration (otherwise output coordinates)

`b`: current direction is up+right. There was a complementary `a` atom, but removing it saved 5 bytes.
> 3 votes

# Answer
# Charcoal, 41 bytes

```
ＮθＦＮＦθ⊞υ⟦⁺ικ§⟦ικ⟧⁺ικκι⟧≔⟦⟧ηＷ⁻υη⊞η⌊ιＩＥη✂ι²

```

Try it online! Link is to verbose version of code. Port of @JonathanAllen's Jelly answer. Explanation:

```
ＮθＦＮＦθ⊞υ⟦⁺ικ§⟦ικ⟧⁺ικκι⟧

```

Generate a list of coordinates and their sort order.

```
≔⟦⟧ηＷ⁻υη⊞η⌊ι

```

Sort them.

```
ＩＥη✂ι²

```

Output just the coordinates.

38 bytes using the newer version of Charcoal on ATO:

```
Ｎθ≔ΣＥＮＥθ⟦⁺ιλ§⟦ιλ⟧⁺ιλλι⟧ηＷ⁻ηυ⊞υ⌊ιＩＥυ✂ι²

```

Attempt This Online! Link is to verbose version of code.

I also tried a canvas-walking approach but that weighed in at a massive 69 bytes:

```
ＵＯＮＮ*≔⁵θ⊞υ⟦ⅈⅉ⟧Ｗ№ＫＭ*«≔⊟Φ⟦⁻⁶÷×³⊖θ²÷×³⊖θ²θ⟧℅⌊ＫＤ²✳κι✳ιψ⊞υ⟦ⅈⅉ⟧¿⁻ιθ≦⁻⁶θ»⎚Ｉυ

```

Try it online! Link is to verbose version of code.
> 2 votes

# Answer
# 05AB1E, 13 bytes

```
Ý€¨`âΣODyRsè‚

```

Input as a pair `[w,h]`. Uses 0-based output.

Port of *@JonathanAllan*'s Jelly answer, so make sure to upvote him as well!
Unfortunately, this approach doesn't port too well to 05AB1E, since it's almost double the byte-count of his answer.. :/

Try it online or verify all test cases.

**Explanation:**

```
Ý        # Convert the values in the (implicit) input-pair to a list in the range [0,v]
 €¨      # Remove the last value from each to make the ranges [0,v)
         # (note: we can't use `L` instead of `Ý€¨` for a [1,v]-ranged list, since it
         # would result in [1,0] for input 0)
   `     # Pop and push both lists separated to the stack
    â    # Take the cartesian product of the two list, creating pairs
Σ        # Sort these pairs by:
 O       #  Take the sum of the pair
  D      #  Duplicate this sum
   y     #  Push the pair again
    R    #  Reverse it (necessary, since 05AB1E uses 0-based indexing instead of 1-based)
     s   #  Swap so one of the sums is at the top of the stack
      è  #  Modular 0-based index it into the pair
       ‚ #  Pair it together with the other sum
         # (after which the sorted list of pairs is output implicitly)

```

The `ODyRsè‚` can be a lot of other alternatives (some examples below), but I've been unable to find anything shorter:

```
OyRyOè‚
RDODŠè‚
O©y®<è‚
ÐO<è‚€O
ÂsOè}ΣO
...

```
> 2 votes

# Answer
# , 63 bytes

```
\(w,h,x=matrix(1:w,w,h),y=col(x))(x+y*1i)[order(s<-x+y,x*s%%2)]

```

Attempt This Online!

Since R is not very good at working with matrices of pairs, this returns the coordinates as the components of a complex number (1-indexed, converted to 0-indexed in the footer for convenience).

Thanks to pajonk for spotting an unnecessary byte.
> 2 votes

---
Tags: code-golf, grid
---


title: Sum the powers that be

text:
# Question
Title: Sum the powers that be
A simple but hopefully not quite trivial challenge:

Write a program or function that adds up the `k`th powers dividing a number `n`. More specifically:

* Input: two positive integers `n` and `k` (or an ordered pair of integers, etc.)
* Output: the sum of all of the positive divisors of `n` that are `k`th powers of integers

For example, 11! = 39916800 has six divisors that are cubes, namely 1, 8, 27, 64, 216, and 1728. Therefore given inputs `39916800` and `3`, the program should return their sum, `2044`.

Other test cases:

```
{40320, 1} -> 159120
{40320, 2} -> 850
{40320, 3} -> 73
{40320, 4} -> 17
{40320, 5} -> 33
{40320, 6} -> 65
{40320, 7} -> 129
{40320, 8} -> 1
{46656, 1} -> 138811
{46656, 2} -> 69700
{46656, 3} -> 55261
{46656, 4} -> 1394
{46656, 5} -> 8052
{46656, 6} -> 47450
{46656, 7} -> 1
{1, [any positive integer]} -> 1

```

This is code golf, so the shorter your code, the better. I welcome golfed code in all kinds of different languages, even if some other language can get away with fewer bytes than yours.

# Answer
# 05AB1E, 9 bytes

```
DLImDŠÖÏO

```

Try it online!

**Explanation**

Example input `46656, 3`

```
D          # duplicate first input
           # STACK: 46656, 46656
 L         # range [1 ... first input]
           # STACK: 46656, [1 ... 46656]
  Im       # each to the power of second input
           # STACK: 46656, [1, 8, 27 ...]
    D      # duplicate
           # STACK: 46656, [1, 8, 27 ...], [1, 8, 27 ...]
     Š     # move down 2 spots on the stack
           # STACK: [1, 8, 27 ...], 46656, [1, 8, 27 ...]
      Ö    # a mod b == 0
           # STACK: [1, 8, 27 ...], [1,1,1,1,0 ...]
       Ï   # keep only items from first list which are true in second
           # STACK: [1, 8, 27, 64, 216, 729, 1728, 5832, 46656]
        O  # sum
           # OUTPUT: 55261

```
> 13 votes

# Answer
## Mathematica, 28 bytes

```
Tr[Divisors@#⋂Range@#^#2]&

```

Unnamed function taking `n` and `k` as inputs in that order.
> 7 votes

# Answer
# Jelly, ~~7~~ 6 bytes

-1 byte thanks to Dennis (traverse an implicit range)
A clever efficiency save **also** by Dennis at **0-byte cost**
(Previously `ÆDf*€S` would filter keep those divisors that are a power of **k** of any natural number up to **n**. But note that **n** can only ever have a divisor of **ik** if it has a divisor of **i** anyway!)

```
ÆDf*¥S

```

**Try it online!**

### How?

```
ÆDf*¥S - Main link: n, k
ÆD     - divisors of n  -> divisors = [1, d1, d2, ..., n]
    ¥  - last two links as a dyadic chain
  f    -     filter divisors keeping those that appear in:
   *   -     exponentiate k with base divisors (vectorises)
       - i.e. [v for v in [1, d1, d2, ..., n] if v in [1^k, d1^k, ..., n^k]]
     S - sum

```
> 6 votes

# Answer
# Python 2, ~~54~~ 52 bytes

```
lambda x,n:sum(i**n*(x%i**n<1)for i in range(1,-~x))

```

Thanks @Rod for cutting off 2 bytes.
> 5 votes

# Answer
# Haskell, ~~37 35~~ 34 bytes

```
n!k=sum[x^k|x<-[1..n],n`mod`x^k<1]

```

Try it online! Usage:

```
Prelude> 40320 ! 1
159120

```

The code is quite inefficient because it always computes `1^k, 2^k, ..., n^k`.

**Edit:** Saved one byte thanks to Zgarb.

**Explanation:**

```
n!k=             -- given n and k, the function ! returns
 sum[x^k|        -- the sum of the list of all x^k
   x<-[1..n],    -- where x is drawn from the range 1 to n
   n`mod`x^k<1]  -- and n modulus x^k is less than 1, that is x^k divides n

```
> 5 votes

# Answer
## Ruby, 45 bytes

```
->n,m{(1..n).reduce{|a,b|n%(c=b**m)<1?a+c:a}}

```

Would be shorter using "sum" in Ruby 2.4. Time to upgrade?
> 4 votes

# Answer
# MATL, 10 bytes

```
t:i^\~5M*s

```

Try it online!

### How it works

Example with `46656`, `6`.

```
t      % Implicitly input n. Duplicate
       % STACK: 46656, 46656
:      % Range
       % STACK: 46656, [1 2 ... 46656]
i      % Input k
       % STACK: 46656, [1 2 ... 46656], 6
^      % Power, element-wise
       % STACK: 46656, [1 64 ... 46656^6]
\      % Modulo
       % STACK: [0 0 0 1600 ...]
~      % Logically negate
       % STACK: [true true true false ...]
5M     % Push second input to function \ again
       % STACK: [true true true false ...], [1^6 2^6 ... 46656^6]
*      % Multiply, element-wise
       % STACK: [1 64 729 0 ...]
s      % Sum of array: 47450
       % Implicitly display

```
> 4 votes

# Answer
# Perl 6, 39 bytes

```
->\n,\k{sum grep n%%*,({++$**k}...*>n)}

```

### How it works

```
->\n,\k{                              }  # A lambda taking two arguments.
                        ++$              # Increment an anonymous counter
                           **k           # and raise it to the power k,
                       {      }...       # generate a list by repeatedly doing that,
                                  *>n    # until we reach a value greater than n.
            grep n%%*,(              )   # Filter factors of n from the list.
        sum                              # Return their sum.

```

Try it
> 4 votes

# Answer
# JavaScript (ES7),  ~~56 53~~  47 bytes

Expects `(n)(k)`.

```
n=>k=>eval("for(i=t=0;i++<n;)t+=n%i**k?0:i**k")

```

Try it online!
> 3 votes

# Answer
# Python 2, 50 bytes

```
f=lambda n,k,i=1:n/i and(n%i**k<1)*i**k+f(n,k,i+1)

```

Try it online! Large inputs may exceed the recursion depth depending on your system and implementation.
> 3 votes

# Answer
# Japt, 10 bytes

*Saved lots of bytes thanks to @ETHproductions*

```
òpV f!vU x

```

## Explanation

```
òpV f!vU x
ò           // Creates a range from 0 to U
 pV         // Raises each item to the power of V (Second input)
    f       // Selects all items Z where
     !vU    //   U is divisible by Z
            //   (fvU would mean Z is divisible by U; ! swaps the arguments)
         x  // Returns the sum of all remaining items

```

Test it online!
> 2 votes

# Answer
# Scala 63 bytes

```
(n:Int,k:Int)=>1 to n map{Math.pow(_,k).toInt}filter{n%_==0}sum

```
> 2 votes

# Answer
## JavaScript (ES7), ~~49~~ 46 bytes

```
n=>g=(k,t=i=0,p=++i**k)=>p>n?t:g(k,t+p*!(n%p))

```
> 2 votes

# Answer
# APL (Dyalog Classic), 14 bytes

```
+/*⍨∘⍳(⊣×0=|)⊢

```

Try it online!

Takes the power as the left argument and the number as the right. Even at 128-bit precision, the last couple of test cases exceed the max int size.

### Explanation:

```
     ⍳            ⍝ The range 1 to right argument
  *⍨∘             ⍝ Each raised to the power of the left argument
      (     )⊢    ⍝ Apply the train to this and the right argument
       ⊣×         ⍝ Multiply each power
         0=|      ⍝ By if the right argument is divisible by it
+/                ⍝ And sum

```
> 2 votes

# Answer
# Pip, 15 bytes

```
$+Ya%_FN(\,a)Eb

```

Try It Online!
> 2 votes

# Answer
# PHP, 86 bytes

```
$n=$argv[1];$k=$argv[2];for($i=1;$i<=$n**(1/$k);$i++)if($n%$i**$k<1)$s+=$i**$k;echo$s;

```

Try it here !

**Breakdown :**

```
$n=$argv[1];$k=$argv[2];       # Assign variables from input
for($i=1;$i<=$n**(1/$k);$i++)  # While i is between 1 AND kth root of n
    if($n%$i**$k<1)            #     if i^k is a divisor of n
        $s+=$i**$k;            #         then add to s
echo$s;                        # echo s (duh!)

```
> 1 votes

# Answer
# CJam, 20 bytes

Probably not optimally golfed, but I don't see any obvious changes to make...

```
ri:N,:)rif#{N\%!},:+

```

Try it online!
> 1 votes

# Answer
# Jelly, 8 bytes

```
R*³%$ÐḟS

```

Try it online!

(Credit not mine.)
> 1 votes

# Answer
# Bash \+ Unix utilities, 44 bytes

```
bc<<<`seq "-fx=%.f^$2;s+=($1%%x==0)*x;" $1`s

```

Try it online!

Test runs:

```
for x in '40320 1' '40320 2' '40320 3' '40320 4' '40320 5' '40320 6' '40320 7' '40320 8' '46656 1' '46656 2' '46656 3' '46656 4' '46656 5' '46656 6' '46656 7' '1 1' '1 2' '1 3' '1 12' ; do echo -n "$x "; ./sumpowerdivisors $x; done

40320 1 159120
40320 2 850
40320 3 73
40320 4 17
40320 5 33
40320 6 65
40320 7 129
40320 8 1
46656 1 138811
46656 2 69700
46656 3 55261
46656 4 1394
46656 5 8052
46656 6 47450
46656 7 1
1 1 1
1 2 1
1 3 1
1 12 1

```
> 1 votes

# Answer
# Python, 56 bytes

```
lambda n,k:sum(j*(j**k**-1%1==n%j)for j in range(1,n+1))

```

Try it online!

Fairly straightforward. The only noteworthy thing is that `j**k**-1%1` always returns a float in **\[0,1)** while `n%j` always returns a non-negative integer, so they can only be equal if both are **0**.
> 1 votes

# Answer
## Batch, 138 bytes

```
@set s=n
@for /l %%i in (2,1,%2)do @call set s=%%s%%*n
@set/at=n=0
:l
@set/an+=1,p=%s%,t+=p*!(%1%%p)
@if %p% lss %1 goto l
@echo %t%

```

Since Batch doesn't have a power operator, I'm abusing `set/a` as a form of `eval`. Very slow when `k=1`. 32-bit integer arithmetic limits the supported values of `n` and `k`:

```
           n   k
  (too slow)   1
 <1366041600   2
 <1833767424   3
 <2019963136   4
 <2073071593   5
 <1838265625   6
 <1801088541   7
 <1475789056   8
 <1000000000   9
 <1073741824  10
 <1977326743  11
  <244140625  12
 <1220703125  13
  <268435456  14
 <1073741824  15
   <43046721  16
  <129140163  17
  <387420489  18
 <1162261467  19
    <1048576  20
           ...
 <1073741824  30

```
> 1 votes

# Answer
# , 35 bytes

```
function(n,k)sum((a=(1:n)^k)*!n%%a)

```

Try it online!

3 years later, but 6 bytes shorter than the previous R answer.
> 1 votes

# Answer
# Husk, ~~10 9~~ 8 bytes

```
ΣnḊ³m^⁰ḣ

```

Try it online!

-1 byte from Jo King.

-1 more byte from Jo King.

## Explanation

```
ΣnḊ³m^⁰ḣ
       ḣ range 1..n
    m^⁰  each raised to power k
 n       set intersection with
  Ḋ³     divisors of n
Σ        sum the list

```
> 1 votes

# Answer
# Japt `-x`, 9 bytes

```
ÆvX=pV)*X

```

Try it

## 8 bytes

My first pass. Realised as I was about to post it that it's pretty much identical to Oliver's existing solution.

```
opV f@vX

```

Try it

```
ÆvX=pV)*X     :Implicit input of integers U=n & V=k
Æ             :Map each X in the range [0,U)
 v            :  Is U divisible by
  X=          :    Reassign to X
    pV        :    X raised to the power of V
      )       :  End divisibility check
       *X     :  Multiply by X
              :Implicit output of sum of resulting array

```
> 1 votes

# Answer
# Vyxal, 6 bytes

```
K:?e↔∑

```

Try it Online!
> 1 votes

# Answer
# R, 28 bytes direct, 43 bytes for function

if n,k in memory:

```
sum((n%%(1:n)^k==0)*(1:n)^k)

```

for a function:

```
r=function(n,k)sum((n%%(1:n)^k==0)*(1:n)^k)

```
> 0 votes

---
Tags: code-golf, arithmetic, number-theory, integer
---


title: Anti-divisors of a number

text:
# Question
Title: Anti-divisors of a number
Given a positive integer `n`, output all of its anti-divisors in any order.

From OEIS A006272:

> Anti-divisors are the numbers that do not divide a number by the largest possible margin. E.g. 20 has anti-divisors 3, 8 and 13. An alternative name for anti-divisor is unbiased non-divisors.

In other words, `1 < m < n` is an anti-divisor of `n` if either

* `m` is even and `n % m == m/2`, or
* `m` is odd and `n % m` is equal to either `(m-1)/2` or `(m+1)/2`.

Notably, 1 is *not* an anti-divisor of any number because it does not satisfy the phrase "do not divide a number".

Standard rules apply. Shortest code in bytes wins.

## Test cases

```
1 -> []
2 -> []
3 -> [2]
4 -> [3]
5 -> [2, 3]
6 -> [4]
7 -> [2, 3, 5]
8 -> [3, 5]
9 -> [2, 6]
10 -> [3, 4, 7]
18 -> [4, 5, 7, 12]
20 -> [3, 8, 13]
234 -> [4, 7, 12, 36, 52, 67, 156]
325 -> [2, 3, 7, 10, 11, 21, 26, 31, 50, 59, 93, 130, 217]

```

# Answer
> 9 votes
# Python 2, 46 bytes

```
lambda n:[m for m in range(2,n)if-2<n%m*2-m<2]

```

Try it online!

# Answer
> 7 votes
# , ~~32~~ 31 bytes

*Edit: -1 byte thanks to @Dominic van Essen.*

```
\(n,m=1:n)m[(n%%m-m/2)^2<1][-1]
```

Attempt This Online!

Pretty much similar to other answers.

The `n=1` is problematic: we can't use `m=2:n` as this would result in `m=2:1`=`c(2,1)`. So we use `m=1:n` and then remove the first element (`1`) with `[-1]` at the end.

# Answer
> 6 votes
# PARI/GP, 30 bytes

-2 bytes thanks to @xnor.

-1 byte thanks to @pajonk and @Dominic van Essen

```
n->[d|d<-[2..n],(n%d-d/2)^2<1]
```

Attempt This Online!

# Answer
> 5 votes
# Knight, ~~40~~ 34 bytes

*-6 bytes thanks to @Bubbler by looping backwards*

```
;=i=pE P W<1=i-iT&>4^-*2%p i i 2Oi

```

Try It Online!

Outputs each anti-divisor in a separate line.

I feel like there's just way too much whitespace; there must be a some rearrangement that can avoid some of this whitespace lol

# Answer
> 4 votes
# Raku, 31 bytes

```
{grep {1>$_%$^a-$a/2>-1},2..$_}

```

Try it online!

Anonymous code block that takes a number and returns a list.

# Answer
> 4 votes
# Jelly, 8 bytes

```
%RḤ_RỊTḊ

```

Try it online!

Feels... messy, but the best I can think of to reuse the range ties: `Ḋ%Ḥ_Ịʋ@Ƈ`

```
%R          n mod each [1 .. n]
  Ḥ         times 2
   _R       minus each corresponding [1 .. n]
     Ị      in [-1 .. 1]?
      T     Find truthy indices
       Ḋ    and remove the first (always 1).

```

# Answer
> 4 votes
# APL (Dyalog Classic), 23 bytes

```
{1↓⍵{(2>|⍵-2×⍵|⍺)/⍵}⍳⍵}

```

Try it online!

**Usage:**

```
      antidiv←{1↓⍵{(2>|⍵-2×⍵|⍺)/⍵}⍳⍵}
      antidiv 10
3 4 7
      antidiv 325
2 3 7 10 11 21 26 31 50 59 93 130 217

```

# Answer
> 3 votes
# Vyxal, 8 bytes

```
Ḣ'?$%dεṅ

```

Try it Online!

-1 byte thanks to lyxal

# Answer
> 3 votes
# Factor, 61 bytes

```
[ dup [1,b] [ [ mod 2 * ] keep - [-1,1]? ] with filter rest ]

```

Try it online!

One of six variations I tried that all come out to 61 bytes. Went with this one because I've never used `[-1,1]?` in a golf before and I think it's a neat word.

# Answer
> 3 votes
# Regex (ECMAScript 2018 / Python`regex` / .NET), ~~35~~ 31 bytes

```
(?=((x+)\2(x?$))(?<=^\3?\2\1*))

```

Try it online! \- ECMAScript 2018 / Try it online! \- test cases only
Try it online! \- Python `import regex` / Try it online! \- test cases only
Try it online! \- .NET / Try it online! \- test cases only

Takes its input in unary, as a string of `x` characters whose length represents the number. Outputs its result as the list of matches' `\1` captures.

This version takes advantage of variable-length lookbehind that is right-to-left evaluated:

```
                     # tail = conjectured anti-divisor
(?=
    (                # \1 = tail
        (x+)\2(x?$)  # \2 = floor(tail / 2); \3 = tail % 2; tail = 0;
                     # head = input number
    )
    (?<=             # Variable-length lookbehind; read from bottom to top.
        ^            # Assert head == 0
        \3?          # optionally, head -= \3
        \2           # Assert head ≥ \2; head -= \2
        \1*          # head %= \1; due to backtracking this result may also have
                     # a multiple of \1 added to it, but it will not be able to
                     # match in that case since \2+\3 is guaranteed to be less
                     # than \1.
    )
)

```

# Regex (ECMAScript 2018 / Java / Python`regex` / .NET), ~~38~~ 37 bytes

```
(?=((x+)\2(x?)))(?<=(?=^\1*\2\3?$).*)

```

Try it online! \- ECMAScript 2018 / Try it online! \- test cases only
**Try it online! \- Java / Try it online!** \- test cases only
Try it online! \- Python `import regex` / Try it online! \- test cases only
Try it online! \- .NET / Try it online! \- test cases only

Java has variable-length lookbehind, with some limits, including that it's not right-to-left evaluated.

```
                    # tail = conjectured anti-divisor
(?=
    (               # \1 = tail
        (x+)\2(x?)  # \2 = floor(tail / 2); \3 = tail % 2
    )
)
(?<=                # Variable-length lookbehind
    (?=
        ^           # Assert we're at the beginning of the string;
                    # tail = input number
        \1*         # tail %= \1
        \2          # Assert tail ≥ \2; tail -= \2
        \3?         # optionally, tail -= \3
        $           # Assert tail == 0
    )
    .*              # Skip to beginning of string
)

```

# Regex (Perl / PCRE2 / Python`regex`), ~~44~~ 43 bytes

```
(?=((x+)\2(x?)))((?<=(?=^\1*\2\3?$|(?4)).))

```

Try it online! \- Perl / Try it online! \- test cases only
Try it online! \- PCRE2 / Try it online! \- test cases only

Emulates variable-length lookbehind using recursion and fixed-length lookbehind.

# Regex (Perl / PCRE / Python`regex`), ~~46~~ 45 bytes

```
(?=((x+)\2(x?)))((?<=(?=z|^\1*\2\3?$|(?4)).))

```

Try it online! \- Perl / Try it online! \- test cases only
**Try it online! \- PCRE1 / Try it online!** \- test cases only
Try it online! \- PCRE2 / Try it online! \- test cases only

Works around PCRE1 being picky about recursion it thinks can be endless.

Both Perl/PCRE versions work on the latest version of Python`regex`, but not the one on TIO.

# Answer
> 3 votes
# JavaScript (SpiderMonkey), 39 bytes

```
n=>{for(i=n;--i;)n%i-i/2|i<2||print(i)}

```

Try it online!

# Answer
> 3 votes
# Desmos, 40 bytes

```
l=[1...n][2...]
f(n)=l[-2<2mod(n,l)-l<2]

```

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 3 votes
# 05AB1E, 8 bytes

```
L¦ʒ%·yα!

```

Try it online or verify all test cases.

**Explanation:**

```
L         # Push a list in the range [1, (implicit) input]
 ¦        # Remove the leading 1 to make the range [2,input]
  ʒ       # Filter this list by:
   %      #  Modulo the (implicit) input by the current value
    ·     #  Double it
     yα   #  Get the absolute difference with the current value
       !  #  Factorial (1 remains 1; 0 becomes 1; everything else just increases)
          #  (only 1 is truthy in 05AB1E)
          # (after which the filtered list is output implicitly)

```

# Answer
> 3 votes
# Prolog (SWI), ~~54~~ 53 bytes

*Huge thanks to JoKing for helping me out immensely for this answer, from debugging my errors and helping me find solutions to my problems*

*Also -1 byte thanks to JoKing*

```
N+X:-findall(M,(between(2,N,M),(N mod M*2-M)^2<4),X).

```

Try it online!

# Answer
> 3 votes
# Fig, \\$14\log\_{256}(96)\approx\\$ 11.524 bytes

```
Fpax'>2A-h%x#x

```

Try it online!

```
Fpax'>2A-h%x#x
  ax            - Range [1..input]
 p              - Remove the first item to make this [2..input]
F   '           - Filter by (where the current item is x):
          %x#x  -  Modulo x by the input
         h      -  Multiply that by 2
       A-       -  Get the absolute difference between x and that
     >2         -  Is it less than 2?

```

# Answer
> 2 votes
# Java 8, ~~69~~ 64 bytes

```
n->{for(int i=1;++i<n;)if((n%i*2-i)/2==0)System.out.println(i);}

```

-5 bytes thanks to *@Deadcode*

Outputs the results to STDOUT on separated lines.

Try it online.

**Explanation:**

```
n->{                           // Method with integer parameter and no return-type
  for(int i=1;++i<n;)          //  Loop `i` in the range (1,input]:
    if((n%i*2-i)               //   If the input modulo `i`, doubled, minus `i`
       /2                      //   integer-divided by 2
         ==0)                  //   equals 0:
      System.out.println(i);}  //    Print `i` with trailing newline

```

# Answer
> 2 votes
# Haskell, 38 bytes

```
h n=[m|m<-[2..n-1],abs(mod n m*2-m)<2]

```

Try it online!

# Answer
> 2 votes
# Nibbles, 8 bytes (16 nibbles)

```
>>|,$~-!=$*%@$~~

```

```
  |                 # filter
   ,$               # the list 1..input
     ~              # by the falsy results of
       !=           # the abxolute difference between
         $          # each element and
          *   ~     # twice (2 is default value '~' for multiplication)
           %@$      # modulo of input by each element
      -        ~    # minus 1 (1 is default value '~' for subtraction)
                    # (note that zero and negative numbers are falsy);
>>                  # finally remove the first element (always 1)

```

# Answer
> 2 votes
# Brachylog, 16 bytes

```
>.&;.%×₂;.-ȧ<2≤≜

```

A predicate that acts as a generator. Try it online!

### Explanation

Brachylog's clunky arithmetic builtins make it less than ideal for this challenge. Maybe there's a better way to do it.

```
>.&;.%×₂;.-ȧ<2≤≜
>.                The output is less than the input
  &               And the input
   ;.%            Modulo the output
      ×₂          Times 2
        ;.-       Difference with the output
           ȧ      Absolute value
            <2    Is less than 2
              ≤   Which is less than or equal to
               ≜  A specific number
                  Which is the output

```

# Answer
> 2 votes
# Ruby, 36 bytes

```
->n{(2..n).select{(n%_1*2-_1)**2<4}}

```

Attempt This Online!

# Answer
> 2 votes
# Julia 1.0, ~~37~~ 30 bytes

```
~n=filter(m->-1<n%m-m/2<1,2:n)

```

Try it online!

-7 bytes thanks to amelies: improve inequality, pass range directly to filter

# Answer
> 2 votes
# Julia 1.0, ~~30~~ 28 bytes

Golfing further Ashlin Harris's solution formula

```
~n=(N=2:n;@.N[-1<n%N-N/2<1])

```

Try it online!

# Answer
> 1 votes
# MathGolf, 13 bytes

```
╒╞g{_k\%∞-±2<

```

Try it online.

**Explanation:**

```
╒              # Push a list in the range [1, (implicit) input]
 ╞             # Remove the leading 1 to make the range [2,input]
  g            # Filter this list by,
   {           # using an arbitrary large inner code-block:
               #  (implicitly push the filter index and value)
    _          #  Duplicate the value
     k         #  Push the input-integer
      \        #  Swap so the value is at the top again
       %       #  Modulo the input by the value
        ∞      #  Double it
         -     #  Subtract the two values from one another
          ±    #  Get the absolute value of this
           2<  #  Check that this is smaller than 2 (so either 0 or 1)
               # (after which the entire stack is output implicitly as result)

```

# Answer
> 1 votes
# C (gcc), ~~58~~ 52 bytes

```
m;f(n){for(m=1;++m<n;)(n%m*2-m)/2||printf("%d ",m);}

```

Try it online!

*Saved 6 bytes thanks to the suggestion of porting Kevin's answer by Neil!!!*

Port of Kevin Cruijssen's Java answer.

# Answer
> 1 votes
# Charcoal, 16 bytes

```
ＮθＩΦ…²θ‹↔⁻⊗﹪θιι²

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｎθ                  First input as a number
    …               Range from
     ²              Literal integer `2` to
      θ             Input number
   Φ                Filtered where
            θ       Input number
           ﹪        Modulo
             ι      Current value
          ⊗         Doubled
        ↔⁻          Absolute difference with
              ι     Current value
       ‹            Is less than
               ²    Literal integer `2`
  Ｉ                 Vectorised cast to string
                    Implicitly print each value on its own line

```

# Answer
> 1 votes
# lin, 33 bytes

```
.#n.n.<1drop".n.+_ %.~2/ -2^1<".#

```

Try it here!

For testing purposes (use `-i` flag when running locally):

```
1 11 .-> 18 20 234 325 ( ;.$$ ).'
.#n.n.<1drop".n.+_ %.~2/ -2^1<".#

```

## Explanation

Prettified code:

```
.#n .n.< 1drop (.n.+_ %.~ 2/ - 2^ 1< ).#

```

Assuming input *n*.

* `.n.< 1drop` range \[*n*, 2\]
* `(...).#` filter...
    + `.n.+_ %.~ 2/ - 2^ 1<` equivalent to `(n%m - m/2)^2 < 1`

# Answer
> 1 votes
# Perl 5 `-n`, 35 bytes

```
//;map{abs($'%$_*2-$_)<2&&say}2..$_

```

Try it online!

Uses a take on xnor's formula in his python answer.

# Answer
> 1 votes
# x86 64-bit machine code, 26 bytes

```
89 F1 51 8D 44 71 01 99 01 C9 F7 F1 58 83 FA 02 77 01 AB 91 E2 EC FF 4F FC C3

```

Try it online!

Takes \\$n\\$ in ESI and writes the anti-divisors as consecutive 32-bit integers, terminated with a 0, to an address given in RDI.

In assembly:

```
f:  mov ecx, esi
r:  push rcx
    lea eax, [2*rsi+rcx+1]
    cdq
    add ecx, ecx
    div ecx
    pop rax
    cmp edx, 2
    ja s
    stosd
s:  xchg ecx, eax
    loop r
    dec DWORD PTR [rdi-4]
    ret

```

# Answer
> 1 votes
# Python 3, ~~102 91 90~~ 88 bytes

+14 bytes because of Jo King -3 bytes because of booleans
-1 byte because of unintentional non-functional whitespace
-11 bytes because lambdas are small
-1 byte because stray ")"
-2 bytes because of a bug that can be exploited in 3.11

```
lambda n:[m for m in range(2,n)if m%2==0and n%m==m/2 or(m%2and n%m in[(m-1)/2,(m+1)/2])]

```

Explained:

```
lambda n:                                                  # create a function for that n where
[                                                          # list begins
m                                                          # pick this item
for m in range(2,n)                                        # in the range 2 to n
if m%2==0                                                  # if it is even
and n%m==m/2                                               # and fits condition 1
or(m%2==1                                                  # or if it is odd
and n%m in[(m-1)/2,(m+1)/2])                               # and is in one of the 2 possibilities of condition 2
]                                                          # close list
)                                                          # print is done

```

NOTE: This will be broken in a future version of Python 3.

# Answer
> 1 votes
# Japt `-f`, 12 bytes

```
ÊÉ©AìøUaN%UÑ

```

Try it

## Without Flags, 13 bytes

```
õ ÅkÈaU%XÑ ÊÉ

```

Try it

```
ÊÉ©AìøUaN%UÑ     :Implicit filter of each U in range [0,input)
Ê                :Factorial
 É               :Subtract 1
  ©              :Logical AND with
   A             :10
    ì            :To digit array
     ø           :Contains?
      Ua         :  Absolute difference of U and
        N        :    Array of all inputs (singleton, in this case)
         %U      :    Mod U
           Ñ     :    Multiplied by 2

```

```
õ ÅkÈaU%XÑ ÊÉ     :Implicit input of integer U
õ                 :Range [1,U]
  Å               :Remove first element
   k              :Remove elements that return true
    È             :When passed through the following function as X
     a            :  Absolute difference with
      U%XÑ        :    U mod X times 2
           Ê      :  Factorial
            É     :  Subtract 1

```

# Answer
> 1 votes
# Go, 119 bytes

```
func f(n int)(a[]int){for i:=2;i<n;i++{k:=n%i
if i%2<1&&k==i/2||i%2>0&&(k==(i-1)/2||k==(i+1)/2){a=append(a,i)}}
return}

```

Attempt This Online!

# Answer
> 1 votes
# \>\<\>, 31 bytes

```
!\:1-:2(?;::{:@}%2*-:*1)?
o\:na

```

Try it online

# Answer
> 0 votes
# Pip `-p`, 15 bytes

```
a%_AD_/2<1FI2,a

```

Try It Online!

### Explanation

```
a%_AD_/2<1FI2,a
              a  Command-line argument
            2,   Range from 2 (inclusive) to that number (exclusive)
          FI     Filter by this function:
a%_                Program argument (number) mod function argument (anti-divisor candidate)
   AD              Absolute difference with
     _/2           Function argument divided by 2
        <1         Is less than 1

```

---
Tags: code-golf, math, number-theory
---


title: "Prime" pyramid

text:
# Question
Title: "Prime" pyramid
The pyramid begins with the row `1 1`. We'll call this row 1. For each subsequent row, start with the previous row and insert the current row number between every adjacent pair of numbers that sums to the current row number. $$ 1\quad1\\ 1\quad\color{red}{2}\quad1\\ 1\quad\color{red}{3}\quad2\quad\color{red}{3}\quad1\\ 1\quad\color{red}{4}\quad3\quad2\quad3\quad\color{red}{4}\quad1\\ 1\quad\color{red}{5}\quad4\quad3\quad\color{red}{5}\quad2\quad\color{red}{5}\quad3\quad4\quad\color{red}{5}\quad1\\ 1\quad\color{red}{6}\quad5\quad4\quad3\quad5\quad2\quad5\quad3\quad4\quad5\quad\color{red}{6}\quad1\\ \cdots $$

This pyramid is an example of a false pattern. It seems to encode the prime numbers in the lengths of its rows, but the pattern breaks down later on. You may wish to learn more about this sequence from a recent Numberphile video which is the inspiration for this question.

## Task

Output the sequence. You may do so in any of the following ways:

| Method | Example input | Example output |
| --- | --- | --- |
| The infinite sequence as rows. We must be able to tell the rows apart somehow. | - | 1 1
1 2 1
1 3 2 3 1
1 4 3 2 3 4 1
... |
| The infinite sequence as numbers, top to bottom, left to right. | - | 1 1 1 2 1 1 3... |
| The first \\$n\\$ rows of the pyramid, 1-indexed. We must be able to tell the rows apart somehow. | 3 | 1 1
1 2 1
1 3 2 3 1 |
| The first \\$n\\$ rows of the pyramid, 0-indexed. We must be able to tell the rows apart somehow. | 3 | 1 1
1 2 1
1 3 2 3 1
1 4 3 2 3 4 1 |
| The first \\$n\\$ numbers in the pyramid, 1-indexed. | 4 | 1 1 1 2 |
| The first \\$n\\$ numbers in the pyramid, 0-indexed. | 4 | 1 1 1 2 1 |
| The \\$n\\$th row in the pyramid, 1-indexed. | 2 | 1 2 1 |
| The \\$n\\$th row in the pyramid, 0-indexed. | 2 | 1 3 2 3 1 |
| The \\$n\\$th number in the pyramid, 1-indexed. | 7 | 3 |
| The \\$n\\$th number in the pyramid, 0-indexed. | 7 | 2 |

## Rules

* Please specify which of the above methods your answer uses.
* Output format is highly flexible. It may take the form of your language's collection type, for instance.
* Sequence rules apply, so infinite output may be in the form of a lazy list or generator, etc.
* This is , so the answer with the fewest bytes (in each language) wins.
* Standard loopholes are forbidden.

# Answer
> 10 votes
# Python 2, ~~52~~ ~~50~~ 48 bytes

*-1 byte thanks to @loopy walt*

Takes as input an integer \\$ n \\$ and outputs the \\$ n^{th} \\$ row. Based on the Wikipedia formula for the Farey sequence.

```
f=lambda n,b=1,d=1:1/d%b*[1]or[d]+f(n,d+n,n-b%d)

```

Try it online!

# Answer
> 8 votes
# K (ngn/k), 26 bytes

Returns the \\$n\\$th row, 0-indexed.

```
1 1{x?[;;y]/|&y=+':x}/2+!:

```

Try it online!

A very literal implementation of the construction described in the challenge.

`2+!:` Integers from 2 to input+1. These are the row numbers to insert.
`1 1{...}/` Using `1 1` as a seed, reduce the range of integers left to right.

`+':x` Sums of adjacent elements in the last row. The first value in the result will be 0+ first value.
`&y=` Indices where this is equal to the new row number.
`|` Reverse the list of indices. We will insert the row numbers one after the other, inserting from left to right would mess up later indices.
`x?[;;y]/` Starting with the last row, insert the new row number at each of the indices.

# Answer
> 8 votes
# Jelly, 8 bytes

```
!:Żg$$fR

```

A monadic Link that accepts a positive integer, \\$n\\$, and yields the \\$n\\$th row as a list of positive integers.

**Try it online!**

### How?

```
!:Żg$$fR - Link: integer, n                  e.g. 4
!        - factorial (n)                          24
     $   - last two links as a monad - f(x=n!):
    $    -   last two links as a monad - f(x):
  Ż      -     zero-range (x)                     [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24]
   g     -     (that) greatest common divisor (x) [24, 1, 2, 3, 4, 1, 6, 1, 8, 3, 2, 1,12, 1, 2, 3, 8, 1, 6, 1, 4, 3, 2, 1,24]
 :       -   (x) integer divide (that)            [ 1,24,12, 8, 6,24, 4,24, 3, 8,12,24, 2,24,12, 8, 3,24, 4,24, 6, 8,12,24, 1]
       R - range (n)                              [ 1, 2, 3, 4]
      f  - filter keep                            [ 1,                4,    3,          2,          3,    4,                1]
                                                = [ 1, 4, 3, 2, 3, 4, 1]

```

# Answer
> 6 votes
# Wolfram Language (Mathematica), 26 bytes

```
Denominator@*FareySequence

```

Try it online!

Inputs \\$n\\$ and returns the \\$n\\$th row, 1-indexed.

---

# Wolfram Language (Mathematica), 33 bytes

```
1||1//.x_||y_/;x+y<=#:>x||x+y||y&

```

Try it online!

---

# Wolfram Language (Mathematica), 39 bytes

```
Cases[#!/GCD[Range[0,#!],#!],a_/;a<=#]&

```

Try it online!

# Answer
> 6 votes
# Julia 0.7, ~~40~~ 39 bytes

```
!n=(a=(p=lcm(1:n))./gcd.(p,0:p))[a.<=n]

```

Try it online!

Thanks to alephalpha for a saved byte.

# Answer
> 5 votes
# PARI/GP, 35 bytes

```
n->[d|i<-[0..n!],n>=d=n!/gcd(n!,i)]

```

Inputs \\$n\\$ and returns the \\$n\\$th row, 1-indexed.

Attempt This Online!

# Answer
> 4 votes
# JavaScript (ES10), 61 bytes

Returns the \\$n\\$-th row (1-indexed), as an array.

This version naively builds all rows up to the requested one.

```
f=(n,a=[r=1,1])=>r++<n?f(n,a.flatMap(v=>n+(n=v)^r?v:[r,v])):a

```

Try it online!

---

# JavaScript (ES6), 43 bytes

*-1 thanks to @loopywalt*

Returns the \\$n\\$-th row (1-indexed), as a comma-separated string.

This is a port of dingledooper's answer.

```
f=(n,b=n,d=1)=>n*~d+b?d+[,f(n,d+n,n-b%d)]:1

```

Try it online!

# Answer
> 4 votes
# 05AB1E, ~~13~~ 9 bytes

-4 bytes porting *@JonathanAllan*'s Jelly answer, also outputting the \\$n^{th}\\$ row based on input \\$n\\$ (so make sure to upvote him as well!):

```
!ÐÝδ¿÷ILÃ

```

Try it online or verify the first 8 rows. (The footer `ï` casts strings to integers, so the output looks better. Feel free to remove it to see the outputs as strings.)

**Explanation:**

```
!         # Get the factorial of the (implicit) input-integer
 Ð        # Triplicate it
  Ý       # Pop one, and push a list in the range [0,input!]
   δ      # Apply double-vectorized, mapping over the list using another input! as
          # argument:
    ¿     #  Get the greatest common divisor of the current value and input!
     ÷    # Integer-divide the third input! by each of these GCD's
      IL  # Push a list in the range [1,input]
        Ã # Only keep those values from the list
          # (after which the result is output implicitly)

```

**Original 13 bytes approach that outputs the infinite sequence (although pretty slowly):**

```
X‚[=Dü+.ιNÌLÃ

```

Try it online. (The footer `ï` casts strings to integers, so the output looks better. Feel free to remove it, and change integer `X` to a literal string `1`, to see the outputs as strings.)

**Explanation:**

```
X             # Push a 1
 ‚            # Pair the top two values together. Since the stack only contains a single
              # item and there is no input, it uses it twice to create pair [1,1]
  [           # Start an infinite loop:
   =          #  Print the current list with trailing newline (without popping the list)
    D         #  Duplicate the list
     ü        #  For each overlapping pair:
      +       #   Sum them together
       .ι     #  Interleave the two lists together
         N    #  Push the 0-based loop index
          Ì   #  Increase it by 2
           L  #  Pop and push a list in the range [1,index+2]
            Ã #  Only keep those values from the list

```

# Answer
> 4 votes
# Excel (ms365), 163 bytes

Formula in `B1`:

```
=IFERROR(REDUCE({1,1},SEQUENCE(A1,,2),LAMBDA(a,b,VSTACK(a,LET(x,TAKE(a,-1),y,DROP(x,,-1),HSTACK(TOROW(VSTACK(y,IF(y+DROP(x,,1)=b,b,NA())),2,1),TAKE(x,,-1)))))),"")

```

---

I designed this answer to be complient with the rule:

> *"The first n rows of the pyramid, 0-indexed. We must be able to tell the rows apart somehow."*

---

The idea here is as follows:

* `REDUCE({1,1},SEQUENCE(A1,,2),LAMBDA(a,b,` \- This bit is basically telling Excel to take the input `{1,1}` and recurse the following `SEQUENCE(A1,,2)` times where 'the following' consists of two these two variables. The iteration will now start;
* `VSTACK(a,` \- The iteration will then `VSTACK()` (vertically build) what is in variable 'a' and stack the following to it;
* `LET(x,TAKE(a,-1),y,DROP(x,,-1),HSTACK(TOROW(VSTACK(y,IF(y+DROP(x,,1)=b,b,NA())),2,1),TAKE(x,,-1)))` \- Bulk of the iteration where we use `LET()` to store the last row from 'a' variable, then take all columns but the last and another variable to take all columns but the first. We compare these two arrays to test if the summation of each element would equal 'b' variable. If so, then use array modification to stack these numbers into the correct location.

# Answer
> 3 votes
# Nibbles, 14 bytes (28 nibbles)

```
`.:1 1|;>>+!!:0$@+@:-+<2@

```

Returns the infinite sequence of rows.
Follows the steps in the challenge description.

```
`.:1 1|;>>+!!:0$@+@:-+<2@
`.                          # iterate until unique
  :1 1                      # starting with a list of 1,1
      |;>>+!!:0$@+@:-+<2@   # this function:
           !       :        #   join each element of
                  @         #   this list
            !:0$@+          #   to pairwise sums of this list (with initial 1),
          +                 #   flatten this list of lists,
        >>                  #   and remove the initial 1;
       ;                    #   (remember this list)
      |                     #   now filter this list
                            #   keeping only elements that are >0 (truthy) after
                    -       #   subtracting from
                     +      #   the sum of
                      <2@   #   the first two elements of the remembered list

```

# Answer
> 3 votes
# Haskell, 56 bytes

```
scanl(!)[1,1][2..]
(a:b:t)!i=a:[i|a+b==i]++(b:t)!i
x!i=x

```

Try it online!

Is an infinite list of rows.

If not valid output this is an infinite list of numbers for 61 Bytes.

```
id=<<scanl(!)[1,1][2..]
(a:b:t)!i=a:[i|a+b==i]++(b:t)!i
x!i=x

```

# Answer
> 3 votes
# Vyxal, 9 bytes

```
¡Dʀvġḭ?ɾ↔

```

Try it Online!

Port of Jonathan Allan's Jelly answer

```
¡D        # n!, 3 times
   vġ     # Gcd with
  ʀ       # Range(0, n+1)
     ḭ    # Integer divide n by that
      ?ɾ↔ # Keep those from range(1, n+1)

```

# Answer
> 2 votes
# Python, 73 bytes

```
a=x,=1,
while[print(1,*a)]:a=sum(([x+y][x+y+~a[0]:]+[x:=y]for y in a),[])

```

Attempt This Online!

Prints forever.

Naive implementation. Feel a bit silly, since everybody else seems to do something clever.

# Answer
> 2 votes
# Charcoal, 27 bytes

```
Ｎθ⊞υ¹Ｗ⁼¹№υ¹⊞υ⁻θ﹪⁺θ§υ±²↨υ⁰Ｉυ

```

Try it online! Link is to verbose version of code. Outputs the `n`th row. Explanation: Based on @dingledooper's formula.

```
Ｎθ

```

Input `n`.

```
⊞υ¹

```

Start with `1` as the first term in the `n`th row.

```
Ｗ⁼¹№υ¹

```

Repeat until there are two `1`s in the row.

```
⊞υ⁻θ﹪⁺θ§υ±²↨υ⁰

```

Calculate the next term as `n-(n+b)%d` where `d` is the previous term and `b` is the penultimate term. Note that on the first loop there is no penultimate term so cyclic indexing gives `b` a value of `1` but `d=1` so the result is `n` anyway.

```
Ｉυ

```

Output all of the terms in the `n`th row.

A naive approach takes 34 bytes:

```
Ｆ²⊞υ¹Ｆ…·²Ｎ≔ΣＥυΦ⟦ικ⟧∨ν∧λ⁼ι⁺κ§υ⊖λυＩυ

```

Attempt This Online! Link is to verbose version of code. Outputs the `n`th row. Explanation:

```
Ｆ²⊞υ¹

```

Start with `[1, 1]` as the first row.

```
Ｆ…·²Ｎ

```

Loop over the remaining rows.

```
≔ΣＥυΦ⟦ικ⟧∨ν∧λ⁼ι⁺κ§υ⊖λυ

```

Insert the current row number into the list at the appropriate places.

```
Ｉυ

```

Output the final list.

# Answer
> 2 votes
# Retina 0.8.2, 71 bytes

```
.+
$*
1
,1$`
^
1,1¶
{`\b(1+)(?=(,1+)\b.*¶\2\1\b)
$1$2$1
}`¶,1+
¶
1+
$.&

```

Try it online! Outputs the `n`th row but link is to test suite that outputs the first `n` rows. Explanation:

```
.+
$*

```

Convert `n` to unary.

```
1
,1$`

```

Create a list from `1` to `n`.

```
^
1,1¶

```

Start with `[1, 1]` as the first row.

```
{`
}`

```

Loop over each row.

```
\b(1+)(?=(,1+)\b.*¶\2\1\b)
$1$2$1

```

Insert the current index between every pair of adjacent values with that as its sum.

```
¶,1+
¶

```

Remove the current index so that the next loop uses the next index.

```
1+
$.&

```

Convert to decimal.

# Answer
> 2 votes
# Haskell, 63 bytes

```
scanl(#)[1,1][2..]
(a:t@(b:_))#r|r==a+b=a:r:t#r|0<1=a:t#r
l#_=l

```

The first line generates a lazy infinite list of rows. Try it online!

### Explanation

The core of the solution is the operator `#`, which takes a list of numbers (the previous row) and an integer (the next row number) and recursively computes the next row.

```
-- If the first argument is a list with at least two elements, unpack it as
-- follows: first element is a, all but first element is t, second element is b
-- Second argument is r
(a:t@(b:_)) # r
-- If r equals a+b, prepend a and r to the result of a recursive call on t
  | r == a+b  = a:r:(t#r)
-- Else, just prepend a
  | otherwise = a:(t#r)

-- If the first argument has fewer than two elements, return it unchanged
l # _ = l

```

Then, to generate the infinite list of rows, we start from `[1,1]` and do a left scan over increasing row numbers:

```
scanl (#) [1,1] [2..]

```

# Answer
> 1 votes
# Pyth, 24 bytes

```
JU2VQ
=-.iJm*qhNdd+VtJJ0

```

Try it online!

Prints the first \\$n\\$ rows as lists.

### Explanation

```
JU2                        assign J to [0, 1]
   VQ                      for N in range eval(input())
                           print
     =   J                 assign J to
      -               0    remove zeros from
       .iJ                 interleave J with
          m*qhNdd          if not N map to 0
                 +VtJJ     pairwise sums of J

```

# Answer
> 1 votes
# Zsh, 92 ~~100~~ bytes

```
p=(1 1)
for j ({2..$1})<<<$p&&p=(`for i ({1..$#p})echo $p[i] ${$((p[i]+p[i+1]==j?j:0)):#0}`)

```

Try it Online! ... ~~100 bytes~~

# Answer
> 1 votes
# C (gcc), 82 bytes

```
o;g(n,b,d){o=n*~d+b?asprintf(&o,"%d %s",d,g(n,d+n,n-b%d)),o:"1";}f(n){n=g(n,n,1);}

```

Try it online!

C port of dingledooper's answer.

# Answer
> 1 votes
# Ruby, 40 bytes

This is a port of dingledooper's answer and Arnauld's answer.

```
->n,b,d=1{b+n*~d<0?[d,f[n,d+n,n-b%d]]:1}

```

Attempt This Online!

---
Tags: code-golf, sequence, number-theory
---