title: Is it irrational?

text:
# Question
Title: Is it irrational?
Your task is to make a program that decides if a real number between 0 and 1 is irrational or not. As stated, this is obviously impossible, so instead we will use the following definition:

`p` is your program, which takes in a decimal expansion of a number (list of integers), and returns 0 (≈Rational) or 1 (≈Irrational). If `x` is an irrational number, then \\$\limsup\limits\_{n\rightarrow\infty}p(x\[:n\])=1\\$, and if `x` is rational the limit superior has to be 0. \\$x\[:n\]\\$ means the truncated decimal expansion, which is just the first `n` digits after the decimal point.

Or in other words, iff `x` is rational, there should be some `n` such that all prefixes longer than `n` return `Rational`.

This is , so shortest code wins. Also, standard rules apply, so instead of outputting 0 or 1, you can output true,false, "Irrational", "Rational", etc. As we know, \\$0.999...=1\\$, so you can assume that the decimal expansion doesn't contain a trail of repeating 9s. Instead of decimal, you can use binary. The input list is non-empty.

# Explanation

Your program will receive a list/string of decimal digits corresponding to a truncated decimal expansion of that real number. For example, if we had the real number `0.31415926...`, the program could receive `[3,1,4]` or `[3]` or `[3,1,4,1,5,9,2]` etc. as input. The program then has to guess whether the real number is irrational or not.

Of course, it's impossible to always guess correctly. What matters is what happens when the input length increases (the limiting behavior). Let's use the **rational** number `8/13=0.6153846153846153846153846...` as example. If we gave the program the first three digits `[6,1,5]`, it might (incorrectly) guess that the number is irrational. But if we gave the program at least 30 digits, it might correctly guess (every time) that the number is rational.

In other words, if your program is given the decimal expansion of a rational number \\$q\\$, there must be some \\$n\\$ so that if at least \\$n\\$ digits are given to your program, it will always return `Rational`.

For irrational numbers the opposite is true. For every irrational number \\$r\\$ there must be infinitely many \\$n\\$ so that if you give the first \\$n\\$ digits of \\$r\\$ as input, the program returns `Irrational`.

# Implementation hints

Every rational number has a repeating decimal expansion and all irrational numbers have non-repeating decimal expansions.

# Possible program execution ("test cases")

```
# 41/333 = 0.123123123123...
[1] -> Rational
[1,2] -> Rational
[1,2,3] -> Irrational
[1,2,3,1] -> Irrational
[1,2,3,1,2] -> Irrational
[1,2,3,1,2,3] -> Rational
[1,2,3,1,2,3,1] -> Rational
[1,2,3,1,2,3,1,2] -> Rational
[1,2,3,1,2,3,1,2,3] -> Rational
[1,2,3,1,2,3,1,2,3,1] -> Rational
[1,2,3,1,2,3,1,2,3,1,2] -> Rational
[1,2,3,1,2,3,1,2,3,1,2,3] -> Rational
[1,2,3,1,2,3,1,2,3,1,2,3,1] -> Rational
# pi/10 = 0.31415926...
[3] -> Rational
[3,1] -> Rational
[3,1,4] -> Irrational
[3,1,4,1] -> Irrational
[3,1,4,1,5] -> Irrational
[3,1,4,1,5,9] -> Irrational
[3,1,4,1,5,9,2] -> Irrational
[3,1,4,1,5,9,2,6] -> Irrational
# 7/24 = 0.291666666...
[2] -> Rational
[2,9] -> Rational
[2,9,1] -> Irrational
[2,9,1,6] -> Irrational
[2,9,1,6,6] -> Irrational
[2,9,1,6,6,6] -> Rational
[2,9,1,6,6,6,6] -> Rational
[2,9,1,6,6,6,6,6] -> Rational
[2,9,1,6,6,6,6,6,6] -> Rational
[2,9,1,6,6,6,6,6,6,6] -> Rational
[2,9,1,6,6,6,6,6,6,6,6] -> Rational
# 0.10110000111111110...
[1] -> Rational
[1,0] -> Rational
[1,0,1] -> Irrational
[1,0,1,1] -> Rational
[1,0,1,1,0] -> Irrational
[1,0,1,1,0,0] -> Irrational
[1,0,1,1,0,0,0] -> Irrational
[1,0,1,1,0,0,0,0] -> Rational
[1,0,1,1,0,0,0,0,1] -> Irrational
[1,0,1,1,0,0,0,0,1,1] -> Irrational
[1,0,1,1,0,0,0,0,1,1,1] -> Irrational
[1,0,1,1,0,0,0,0,1,1,1,1] -> Irrational
[1,0,1,1,0,0,0,0,1,1,1,1,1] -> Irrational
[1,0,1,1,0,0,0,0,1,1,1,1,1,1] -> Irrational
[1,0,1,1,0,0,0,0,1,1,1,1,1,1,1] -> Irrational
[1,0,1,1,0,0,0,0,1,1,1,1,1,1,1,1] -> Rational
[1,0,1,1,0,0,0,0,1,1,1,1,1,1,1,1,0] -> Irrational
# 333/500 = 0.66600000000...
[6] -> Rational
[6,6] -> Rational
[6,6,6] -> Rational
[6,6,6,0] -> Irrational
[6,6,6,0,0] -> Irrational
[6,6,6,0,0,0] -> Rational
[6,6,6,0,0,0,0] -> Rational
[6,6,6,0,0,0,0,0] -> Rational

```

# Answer
# Jelly, 5 bytes

```
ŒHṪẇṖ

```

A monadic Link that accepts a list and yields `1` (≈rational) or `0` (≈irrational).

**Try it online!** Or see the test-suite (results being the application to each prefix of each input).

### How?

Identify a list, `L`, as rational if the last half is a sublist of `L` without its final element (i.e. appears anywhere earlier).

```
ŒHṪẇṖ - Link: list, L
ŒH    - split L into two halves (first half longer when odd in length)
  Ṫ   - tail -> X = last half of L
    Ṗ - pop L -> Y = L without its final element
   ẇ  - is Y a sublist of X?

```
> 5 votes

# Answer
# Retina 0.8.2, 33 bytes

```
((.)+)$(?<=^(?<-2>.)+\1(?<-2>.)+)

```

Try it online! Link includes test cases. Explanation: Requires that at least the last half of the input is repeated somewhere between it and the start (exclusive). The middle `+` could be changed to `*` to allow matching at the start but I thought it looked prettier this way and it doesn't matter in the long run.
> 4 votes

# Answer
# JavaScript (Node.js), 45 bytes

```
x=>x.match(`^.{0,${x.length>>1}}(.+)\\1{9}$`)

```

Try it online!

Requiring any length have a \*10 loop allowing some left before, so rational number works; not well confirmed on irrational though
> 3 votes

# Answer
# PARI/GP, 41 bytes

```
a->prod(i=1,#a,#Pol(Ser(a)*(1-x^i))>#a/2)
```

Attempt This Online!

```
a->prod(i=1,#a,#Pol(Ser(a)*(1-x^i))>#a/2)

a ->                                         Define a function with argument `a`
   prod(i=1,#a,                         )    Take product, where `i` runs from `1` to the length of `a`
                    Ser(a)                   Convert `a` to (truncated) power series
                          *(1-x^i)           Multiply `1 - x^i`
                Pol(              )          Convert to a polynomial
               #                             Take the length of the polynomial, i.e., degree + 1
                                   >#a/2     Check if the result is larger than half of the length of a

```

Take `a = [2,1,6,1,6]` as an example:

* `Ser(a)` is `2 + x + 6*x^2 + x^3 + 6*x^4 + O(x^5)`.
* When `i = 2`, `Ser(a)*(1-x^i)` is `2 + x + 4*x^2 + O(x^5)`.
* `#Pol(Ser(a)*(1-x^2))` is `3`, which is equal to the half of the length of `a`.
* So the result is `0`.
> 3 votes

# Answer
# , ~~69~~ 73 bytes

(or 59 bytes in R≥4.1 by changing two `function` keywords each to `\`)

*Edit: changed approach to give correct output for A003842.*

```
function(x,l=sum(x|1)/2,s=1:l)all(Map(function(i)any(x[l+s]-x[s+i]),s-1))

```

Try it online!

Returns `FALSE` for suspected rational numbers, and `TRUE` for suspected irrational numbers.
Based on approach of Neil's answer: checks whether the second half of the input sequence is identical to any subsequence except itself.
> 3 votes

# Answer
# Husk, 6 bytes

```
§€ho→½

```

Try it online!

Or try it online with a rational test-case with a non-repeating prefix, or try it online with the first few digits of pi, or try it online with the first few digits of A003842.

Ports Neil's answer: checks whether the second half of the input sequence is present within the input without its last digit.

Unfortunately my initial attempt (`ṁoV=½ṫ`, which checked whether the input digits end in a repeated sequence, fails for the non-repeating sequence A003842 \[credit to Bubbler for finding this\]).
> 2 votes

# Answer
# Charcoal, 12 bytes

```
›÷Ｌθ²⌕θ✂θ⊘Ｌθ

```

Try it online! Link is to verbose version of code. Takes input as a string and outputs a Charcoal boolean, i.e. `-` for probably rational, nothing for probably irrational. Explanation:

```
   θ            Input string
  Ｌ             Length
 ÷              Integer divided by
    ²           Literal integer `2`
›               Is greater than
      θ         Input string
     ⌕          Find index of
        θ       Input string
       ✂        Sliced from
           θ    Input string
          Ｌ     Length
         ⊘      Halved

```

(`Slice` truncates its parameters so I don't have to use integer division.)
> 1 votes

# Answer
## Haskell, 57 bytes Invalid solution

```
import Data.List
(==[[]]).intersect<*>map(\a->a++a).tails

```

True for irrational number, False for rational number

I used a different algorithm for this program. This program returns true if the sequence ends with two identical sequence next to each other. For example, this program returns true for \[1,2,3,4,3,4\] because it ends with \[3,4,3,4\], which is \[3,4\] repeated twice.

For rational number, it's obvious that this will return false for large enough string, because rational number always ends with repeating string of digits. However, I don't know if this program still works for irrational number.  Turns out it doesn't work for irrational numbers.

## Haskell, 60 bytes

```
import Data.List
isInfixOf<$>(drop=<<(`div`2).length)<*>init

```

Turns out that the fixed solution is not that worse. This uses the more standard solution: whether the last half of the string still appears anywhere else in the string.
> 1 votes

# Answer
# BQN, 24 bytes

```
(↓⊑˜2⌊∘÷˜≠)⋈⊸∊{∾↑¨↓¯1↓}

```

Try it at BQN online REPL

Ungolfed: for input , checks whether `(SecondHalfOf ) IsOneOf SublistsOf HeadOf` .
Try the ungolfed code here
> 1 votes

---
Tags: code-golf, math, decision-problem, open-ended-function
---


title: Count the Liberties

text:
# Question
Title: Count the Liberties
### Background

This challenge is about the game of Go. Go is a game played on a board with a square grid `N x N`. You don't have to know how to play the game to do this challenge, but if you are interested, google "Tromp-Taylor rules" for a minimal and precise set of rules to play a full game.

Let's use a `4 x 4` board. As the game starts, two players, black (`X`) and white (`O`), alternately place a stone on an empty grid starting with black.

At some point of the game, the board may look like this.

```
. . O .
. X X .
. X . .
. O O .

```

Black has 1 group, and white has 2 groups. A *group* is a group of stones that are connected horizontally or vertically.

```
. X X .
X . X .
X X . .
. . X X

```

Black has 3 groups on this board.

```
. . O .
. X X .
. X . .
. O O .

```

Back to the first example, the upper group of white has 2 liberties and the lower group of white has 3 liberties. *Liberty* is the number of empty spaces connected horizontally or vertically to a group.

```
X . O X
. . . .
. . . O
. . O X

```

There are 3 black groups on this board each with 2, 1, and 0 liberties. In an actual game a group with 0 liberties are taken out of the board, but you don't have to care about that in this challenge.

### Challenge

The input is a `4 x 4` Go board position, where there is 1 black group and any number of white groups.

The output is the number of liberties that the black group has.

The input can be encoded in any way that can hold \\$3^{4\times4}\\$ distinct values.

The output is an integer, when optionally printed, up to base 16.

### Examples

```
. . . .
. X . .
. . . .
. . . .  ->  4

. . . .
. X X .
. . . .
. . . .  ->  6

X X . .
X . . .
. . . .
. . . .  ->  3

X X O .
X O . .
O . . .
. . . .  ->  0

. X X .
. X . X
. X X X
. . . .  ->  8

O X X .
O X . X
O X X X
. O O O  ->  2

O X X O
O X O X
O X X X
. O O O  ->  0

```

The last case is an impossible position in the actual game, but it is valid for this challenge.

# Answer
> 8 votes
# MATL, 10 bytes

```
~Go1Y6Z+*z

```

Try it online!

Takes input as a \\$4\times 4\\$ matrix with `0` representing an empty point, a `1` representing a black stone, and a `2` representing a white stone.

Bonus, contains `Go`!

```
        % implicit input M
~       % logically negate: push matrix of 1s where there are empty points
Go      % Push matrix, mod 2: get matrix of 1s where black stones are
1Y6     % Push [0 1 0; 1 0 1; 0 1 0], the matrix of adjacencies
Z+      % two-dimensional convolution maintaining size
*z      % multiply and count the number of nonzero entries.
        % (implicit) convert to string and display

```

# Answer
> 4 votes
# BQN, 19 bytesSBCS

Takes input as an integer matrix with `1` for empty squares, `2` for white and `3` for black stones.

```
+´∘⥊1⊸=∧3=«˘⌈»˘⌈»⌈«

```

Run online!

`«˘⌈»˘⌈»⌈«` Shift the matrix by one from each of the four directions and take the element-wise maximum.
`3=` For each value in this new matrix, is it equal to 3? This gives 1 for each square adjacent to a black stone on the board.
`1⊸=∧` *And* is the square empty?
`+´∘⥊` Count the 1's by summing.

# Answer
> 3 votes
# Wolfram Language (Mathematica), 56 bytes

```
Count[ListConvolve[{r={0,1,0},1-r,r},#,2,0]^#,_.+_.a,2]&

```

Try it online!

Takes input as a 2d array, with `1` for empty, `0` for white, `a` for black.

# Answer
> 2 votes
# Retina 0.8.2, ~~75~~ 26 bytes

```
(?<=X....|X)_|_(?=X|....X)

```

Try it online! Link includes test suite that converts from double-spaced newline-delimited examples using `.` to comma-delimited strings using `_`. Works with boards of any height. Explanation: Counts the number of `_`s which are either adjacent or exactly 5 characters away from an `X` (which represents one directly above or below).

Edit: Saved 49 bytes thanks to @tsh by hard-coding the size of the board. Previous 75-byte answer works on any rectangular size of board:

```
(?<=X|X(?(1)$)(?<-1>.)*¶.*(?=.(.)*))_|_(?=X|(?<=(.)*.).*¶(?<-2>.)*(?(2)^)X)

```

Try it online! Link includes test suite that accepts double-spaced examples using `.` although code requires `_`. Explanation: Uses .NET balancing groups to count the number of `_`s with any `X` that is adjacent to the left, above, right or below respectively.

# Answer
> 1 votes
# Charcoal, ~~35~~ 32 bytes

```
≔⪫Ｅ⁴Ｓ⸿θＰθ≔⁰ηＦθ«≧⁺∧№ＫＶX⁼ＫＫ.ηι»⎚Ｉη

```

Try it online! Link is to verbose version of code. Only works for boards of height 4, but accepts any width (including variable width). Explanation:

```
≔⪫Ｅ⁴Ｓ⸿θ

```

Input the board. (Save 7 bytes if a JSON string with each line delimited by carriage returns is an acceptable input format, in which case this works for any size of board.)

```
Ｐθ

```

Output the board without moving the cursor.

```
≔⁰η

```

Start with `0` liberties.

```
Ｆθ«

```

Loop over the string.

```
≧⁺∧№ＫＶX⁼ＫＫ.η

```

Increment the number of liberties if this is a `.` with at least one orthogonally adjacent `X`.

```
ι

```

Move to the next character.

```
»⎚Ｉη

```

Clear the canvas and output the final count of liberties.

Edit: Saved 3 bytes by hard-coding the size of the board as suggested by @tsh on my Retina answer. Previous 35-byte answer works for any size of board in human-readable format:

```
ＷＳ⊞υι≔⪫υ⸿θＰθ≔⁰ηＦθ«≧⁺∧№ＫＶX⁼ＫＫ.ηι»⎚Ｉη

```

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings. Explanation: `ＷＳ⊞υι≔⪫υ⸿θ` converts the input into a single carriage-return delimited string, after which the remaining 25 bytes are the same.

# Answer
> 1 votes
# 05AB1E (legacy), ~~12~~ 11 bytes

```
4FTx:øí}J2¢

```

-1 byte thanks to *@emanresu*

Takes a list of strings as input, with `1` for empty spots; `0` for black; and just `O` (could be any character besides `012`) for white.

Try it online or verify all test cases.

**Explanation:**

Uses the legacy version of 05AB1E, because it can zip/transpose on a list of strings, where the new version would require character-matrices. In the new version the `ø` would be `€SøJ` (convert each to a character-list; zip/transpose; join back to strings), so using the legacy saves 3 bytes here.

```
4F     # Loop 4 times:
  T    #  Push 10
   x   #  Double it (without popping): 20
    :  #  Replace all "10" to "20" in the strings of the list
       #  (which uses the implicit input-list in the first iteration)
  øí   #  Rotate the 4x4 block once clockwise:
  ø    #   Zip/transpose; swapping rows/columns
   í   #   Reverse each inner row
 }J    # After the loop: join to have a single string
   2¢  # Count how many 2s are in this string
       # (after which it is output implicitly as result)

```

# Answer
> 1 votes
# Vyxal, 14 bytes

```
4(36₄vV§↵R)∑2O

```

Try it Online!

Messy port of Kevin Cruijssen's 05AB1E answer.

Two things increase the byte count of this:

* We have to explicitly vectorise replace (`V`)
* Transposing creates a character matrix, so we use a more convoluted method.

```
4(        )    # Four times...
  36₄vV        # Replace 36 with 26
       §↵R     # Rotate 90°
           ∑2O # Count the 2s in the result.

```

# Answer
> 1 votes
# Python 3, 121 112 90 bytes

```
def l(b,n=0):
 for i in range(36):
  if b[i]>0==b[i-1]*b[i+1]*b[i-6]*b[i+6]:n+=1
 return n

```

Edit -9 bytes: @LeopardShark outgolfed me with another Python3 answer, but luckily I was able to golf my code 1 byte lower than theirs, albeit by abusing lax input restrictions even more: the flattened 6x6 list is now lengthened to a 68 item list, where the first 32 items are total junk, and simply space the indices out properly.

Edit -22 bytes: @LeopardShark's 73 byter made me realize I could actually use `range(36)` instead of my solution iterating over a string with `ord()`, plus a few tweaks to the conditional, brings this down to 90 bytes, which is I think as short as I can get this code without wholesale copying LeopardShark's solution using `sum()`. But hey! at least the input doesn't need 32 garbage entries at the start of the list anymore.

I feel like there's way better ways to do this, but both getting the right range to iterate on and evaluating the conditional stumped me as to shorter ways than this.

Takes input as an list of length 36, representing a flattened 6x6 grid, where only the central 4x4 actually holds useful data. Black pieces are marked with `0`, whites with `-1`, and empty spaces with `1`. The "padding" on the exterior is also filled with `-1`.

The program just loops through each square in the board, and checks if any of the four adjacent squares are equal to 0. If it is, that square is a liberty, and a counter is incremented.

Working TIO link with test cases now that I've removed the walrus

# Answer
> 1 votes
# Python 3, 71 bytes

```
lambda p:sum(p[x+1]+p[x-1]+p[x+6]+p[x-6]>8 for x in range(36)if p[x]<1)

```

This checks each cell next to a blank one to look for a black stone.

It takes its input as an array of 36 `1` (white), `9` (black) and `0` (empty), with the board surrounded by `1`.

This was much longer (113 B), but des54321’s 6×6 input strategy helped to shorten it.

Thanks to Chris for pointing out that `f=` was unnecessary.

Try it online!

---
Tags: code-golf, game, board-game, go
---


title: Sum of first n terms of this series

text:
# Question
Title: Sum of first n terms of this series
Given a digit `x` (between 0 to 9, inclusive) and a number `n`, calculate the sum of the first `n` terms of the following sequence:

\\$x,10x+x,100x+10x+x,\dots\\$

For example, if `x` is 6 and `n` is 2, then the result will be `6+66` meaning 72.

There can be trailing whitespace in the output but not leading whitespace.

# Answer
> 16 votes
# Python 2, 28 bytes

```
lambda x,n:(10**-~n/9-n)/9*x

```

Try it online!

-6 thanks to @Bubbler and @tsh

Aha the first answer I have used some math

**How?**

Let's call \\$n^{th}\\$ term as \\$y\\$

$$ S\_n=x+(10x+x)+(100x+10x+x)+.....+y\\\= x+(11x)+(111x)+.....+y\\\=\frac{x}{9}(9+99+999+.....+y)\\\=\frac{x}{9}((10-1)+(100-1)+(1000-1)+.....+y)\\\=\frac{x}{9}((10+100+1000+.....+y)-(1+1+1+.....+1))\\\=\frac{x}{9}((10^1+10^2+10^3+...+y)-n)\\\=\frac{x}{9}(\frac{10(10^n-1)}{10 - 1}-n)\\\=\frac{x}{9}(\frac{10(10^n-1)-9n}{9})\\\=\frac{x(10(10^n-1)-9n)}{81} $$

And we get our magic formula!

# Answer
> 11 votes
# Jelly, 3 bytes

```
RḌ×

```

Try it online!

```
RḌ×    Dyadic link; left arg = n, right arg = x
R      [1..n]
 Ḍ     Undecimal, which is the same as 1 + 11 + ... + (n copies of 1)
  ×    Multiply x

```

---

These are the "backports" of the same algorithm into J and APL:

# , 9 bytes

```
*10#.1+i.

```

Try it online!

`1+` is needed because J does not have 1-based range built-in.

# APL (Dyalog Unicode), 6 bytes

```
10⊥×∘⍳

```

Try it online!

*-1 byte thanks to @ovs*

Uses a slightly different algorithm for golfing purposes: multiply `x` to `1..n`, and then evaluate as base 10. This version of the algorithm works in Jelly too: `R×Ḍ`. Try it online!

# Answer
> 10 votes
# JavaScript (Node.js), 24 bytes

```
t=>g=n=>n&&t*n+10*g(n-1)

```

Try it online!

$$ f(n,x)=\sum\_{i=1}^n 10^{n-i}\cdot i\cdot x $$ $$ f(n,x)=nx+10\cdot f(n-1,x) \\ f(0,x)=0 $$

For example, we have:

\\$f(6,3)\\ =6+66+666\\ =6+(60+6)+(600+60+6)\\ =600×1+60×2+6×3\\ =((6×1)×10+6×2)×10+6×3\\ =10\cdot f(6,2)+6×3\\$

# Answer
> 10 votes
# Excel, 29 bytes

```
=SUM(--REPT(A1,SEQUENCE(A2)))

```

`x` is input in `A1` and `n` is input in `A2`. The formula goes anywhere else in the same sheet.

`SEQUENCE(A2)` creates an array of all the values from 1 to `n`.
`REPT(A1,~)` creates an array of strings of `x` repeated an increasing number of times based on the array created from the previous step.
`--REPT(~)` turns those strings into numbers.
`SUM(~)` adds up those numbers.

# Answer
> 8 votes
# Vyxal `R`, ~~3~~ 2 bytes

```
I*

```

Try it Online!

*Thanks to @AaronMiller for -1*

## 3 bytes, `-rs`

```
ƛ⁰ẋ

```

Try it Online!

;)

## Explained

```
ƛ⁰ẋ
ƛ       # For each number n in the range [1, N]:
 ⁰ẋ     #  return x repeated n times (`-r` makes elements take arguments in reverse order)
        # The `-s` flag sums the top of the stack before outputting

```

## 4 bytes, `s` flag

```
ɾ?vẋ

```

Try it Online!

## 5 bytes, flagless

```
ɾ?vẋ∑

```

Try it Online!

# Answer
> 6 votes
# , 11 8 bytes

```
1#.".\@$

```

Try it online!

Assuming I can take the digit as a string...

Taking `3 f '6'` as an example:

* `$` \- Duplicate:

```
'666'

```
* `".\` Evaluate each prefix:

```
6 66 666

```
* `1#.` Sum

```
738

```

# Answer
> 5 votes
# MATLAB/Octave, ~~28~~ 26 bytes

*-2 bytes thanks to Giuseppe*

```
@(x,n)(1:n)*.1.^(1-n:0)'*x

```

Try it online!
Anonymous function.

**How it works**
First of all, sum $$x + (10x + x) + (100x + 10x + x) + ... + (10^{n-1}x + 10^{n-2}x + ... 10x + x)$$ can be transformed to: $$ n\cdot x + 10(n-1)\cdot x + 100(n-2) \cdot x + ... +10^{n-2} \cdot 2 x + 10^{n-1} x $$ which is: $$ x \cdot \sum\_{i=0}^{n-1}(n-i) 10^i = x \cdot \sum\_{i=0}^{n-1}(n-i)\cdot{0.1^{-i}}$$ Having that established:

* `1:n` is vector containing elements , but in reverse order of indexing than above
* `1-n:0` are just indexes of sum above but reversed and negates (so )
* `.1.^(1-n:0)` is then vector containing elements in reversed order of indexing

To get the sum straightforward we would multiply elements of vectors element by element and then sum them like so (whitespace added for readability):

```
sum(  (1:n)  .*   (.1.^(1-n:0))   )

```

However, knowing how matrix multiplication works we can just transpose second vector and by multiplying the matrices:

```
(1:n)  *  (.1.^(1-n:0))'

```

we will get exactly the same result. And at the end we just multiply everything by `x`.

# Answer
> 4 votes
# PowerShell Core, 41 bytes

```
param($x,$n)iex "$(1..$n|%{"+";"$x"*$_})"

```

Try it online!

## Explanations

```
iex "$(...)"          # Run as a command the result of the list below, joined using spaces
1..$n|%{"+";"$x"*$_}  # From 1 to n, build a list containing +,x,+,xx,+,xxx,+,xxxx,...

```

# Answer
> 4 votes
# , ~~34~~ 32 bytes

```
function(d,n)sum(10^(1:n)-1)*d/9

```

Try it online!

$$ x + (10x + x) + (100x + 10x + x) + \ldots = \\ x + 11x + 111x + \ldots = \\ (9x + 99x + 999x + \ldots)/9 = \\ (9+99+999+\ldots)\*x/9 = \\ ((10-1)+(100-1)+(1000-1)+\ldots)\*x/9 = \\ \big\[\sum\_{i=1}^n(10^i-1)\big\]\*x/9 $$

*-2 bytes thanks to @Giuseppe*

---

Using @Wasif's formula:

### , 34 bytes

```
function(d,n)d*(10*(10^n-1)/9-n)/9

```

Try it online!

---

Straightforward approach with strings:

### , ~~43~~ 39 bytes

```
function(d,n)sum(strtoi(strrep(d,1:n)))

```

Try it online!

*-4 bytes thanks to @Giuseppe*

# Answer
> 3 votes
# Jelly, 4 bytes

```
ẋḌƤS

```

Try it online!

## Explanation

```
ẋ     repeat `x` `n` times
  Ƥ   for each prefix
 Ḍ    convert it from digits to a decimal number
   S  and sum

```

# Answer
> 3 votes
# Husk, 3 bytes

```
*dḣ

```

Try it online!

# Answer
> 3 votes
# Raku, 28 17 bytes

```
* *(1 Xx^*+1).sum

```

Golfed by Jo King from 28 byte solution:

* Positional arguments `$^a`, `$^b` replaced by whatever-stars
* `Xx` cross metaoperator responsible for generating `1, 11, 111...`

---

### Original, 28 bytes

```
{$^a*(^$^b+1).map(1 x*).sum}

```

**Explanation**

* `$^a` is `x`, `$^b` is `n`
* `^$^b+1` is shorthand for `0..^$^b+1`, equivalent to `1..$^b`
* `.map(1 x*)` generates `1, 11, 111...`
* `.sum` adds the `n`-long sequence: 1 for `n=1`, 12, 123, etc.

---

### Alternative, 32 bytes

```
{[+] ($^b…1)Z*($^a,* *10…*)}

```

**Explanation**

* `Z*` zip-multiplies two lists, based on the observation that
    + `1E0` appears `n` times
    + `1E1` appears `n-1` times
    + `1E2` appears `n-2` times, etc.

# Answer
> 3 votes
# Python 3, Python 2, 28 bytes

```
lambda x,n:(10**n/.9-n)//9*x

```

Try it online! Try it online!

Unfortunately I cannot add comments so I'm reposting Wasif's solution with a small tweak so that it works in both python versions. While at it, also correct the math.

$$ S\_n=x+(10x+x)+(100x+10x+x)+...+y\\\= x+(11x)+(111x)+...+y\\\=\frac{x}{9}(9+99+999+...+\frac{9y}{x})\\\=\frac{x}{9}((10-1)+(100-1)+(1000-1)+...+(\frac{9y}{x}+1-1))\\\=\frac{x}{9}((10+100+1000+...+(\frac{9y}{x}+1))-(1+1+1+...+1))\\\=\frac{x}{9}((10^1+10^2+10^3+...+10^n)-n)\\\=\frac{x}{9}(\frac{10^{n+1}-10}{9}-n)\\\=\frac{x}{9}(\frac{10(10^n-1)-9n}{9})\\\=\frac{x(10(10^n-1)-9n)}{81} $$

# Answer
> 3 votes
# , 31 bytes

```
function(d,n)10^(1:n-1)%*%n:1*d

```

Try it online!

Ports elementiro's answer.

# Answer
> 2 votes
# Python 3, 43 bytes

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

```

Try it online!

Accepts `x` as a string and `n` as an integer. If that's not acceptable, just use `lambda x,n:sum(int(`x`*-~i)for i in range(n))` in Python 2 for +2 (+5 with `str(x)` in Python 3).

# Answer
> 2 votes
# AWK, 26 bytes

```
{for(;$2--;b+=a)a=a$1}$0=b

```

Try it online!

I had an alternate algorithm I thought might be interesting, but it the code was longer... So this is pretty much a direct translation of the steps in the challenge description.

```
{for(;$2--;    )     }

```

Fir every line of input, the code runs the loop the number of times given by the second input parameter, the `n` value.

```
                a=a$1

```

The body of the loop appends another copy of the first input parameter to the requested digit, meaning the `x` value.

```
           b+=a

```

At the end of each iteration, the accumulator variable `b` is incremented by the current value of the digits placeholder.

```
                      $0=b

```

Finally, once the processing is done, `$0=b` overwrites the input line to display the accumulator value.

The only "trick" here is relying on the way AWK will happily treat variables as both strings and integers. Meaning, you can append digits together and still do mathematical operations using the results.

# Answer
> 2 votes
# Perl 5 `-pal`, 22 bytes

```
map$\+="@F"x$_,1..<>}{

```

Try it online!

# Answer
> 2 votes
# Haskell, 24 bytes

```
n#x=x*div(10*10^n-9*n)81

```

Try it online!

Uses Wasif's formula.

## Haskell, also 24 bytes

```
0#x=0
n#x=n*x+10*(n-1)#x

```

Try it online!

A port of tsh's excellent recursive formula.

# Answer
> 2 votes
# Japt `-x`, 3 bytes

Takes input in reverse order.

```
õçV

```

Try it

```
õçV     :Implicit input of integers U=n & V=x
õ       :Range [1,U]
 çV     :  For each, repeat V that many times
        :Implicit output of sum of resulting array

```

# Answer
> 2 votes
# C (gcc), ~~45~~ 43 bytes

Saved 2 bytes thanks to Olivier Grégoire!!!

```
t;s;f(x,n){for(s=t=0;n--;)s+=t=t*10+x;n=s;}

```

Try it online!

# Answer
> 2 votes
# Factor \+ `math.unicode`, 44 bytes

```
[ [1,b] [ 10^ 1 - swap 9 / * ] with map Σ ]

```

Try it online!

Using the first thing that came to mind, $$ f(x,n)=\sum\_{i=1}^n \frac{x}{9}(10^{i} - 1) $$

# Answer
> 2 votes
# GolfScript, ~~20~~ 21 bytes

```
~:x;0\),(;{'1'*~x*+}%

```

Try It Online!

takes as input a string containing n and x, in that order

### Explanation

```
~:x;0\),(;{'1'*~x*+}%
~                      // parse the input string given
 :x;                   // bind the top value to the x variable
    0\                 // place a zero at the bottom of the stack
      ),(;             // create a list of numbers [1..n]
          {            // begin code block
           '1'*~       // create and evaluate a string of '1's to get the numbers 1, 11, 111...
                x*+    // multiply by x and add to the total (the zero we added)
                   }%  // execute this over every value in the list
                       // implicitly print the stack

```

# Answer
> 2 votes
# C# (Visual C# Interactive Compiler), 83 bytes

```
(a,b)=>Enumerable.Range(1,b).Sum(x=>Enumerable.Range(0,x).Sum(y=>a*Math.Pow(10,y)))

```

Try it online!

# 39 bytes using @Wasif's formula

```
(a,b)=>a*(10*(Math.Pow(10,b)-1)-9*b)/81

```

Try it online!

# 28 bytes using @tsh's formula

```
(a,b)=>b>0?a*b+10*f(a,b-1):0

```

Try it online!

# Answer
> 2 votes
# Zsh, 31 bytes

```
for ((;i++<$2;t+=a))a+=$1
<<<$t
```

Attempt This Online!

# Answer
> 1 votes
# 05AB1E, 3 bytes

```
L×O

```

Try it online!

```
L       -- list [1..input]
 ×      -- string multiply with input
  O     -- sum

```

# Answer
> 1 votes
# Red, 47 bytes

```
func[x n][t: s: 0 loop n[t: t + s: s * 10 + x]]

```

Try it online!

## Alternative, 55 bytes

```
func[x n][t: copy""s: 0 loop n[s: s + to 1 append t x]]

```

Try it online!

# Answer
> 1 votes
# Desmos, ~~30~~ ~~26~~ 25 bytes

```
f(x,n)=x(10^n10-10-9n)/81

```

Try It On Desmos!

Try It On Desmos!(Prettified)

# Answer
> 1 votes
# Retina, 20 bytes

```
.+(.)
*$1
L$v`.+
*
_

```

Try it online! Link includes test cases. Takes `n` as the first input. Note: Struggles for large values of `n` (`5` is just about doable). Explanation:

```
.+(.)
*$1

```

Generate `n` copies of `x`.

```
L$v`.+
*

```

Convert each suffix to unary.

```
_

```

Take the sum and convert to decimal.

# Answer
> 1 votes
# Pip, 8 bytes

```
$+YaX\,b

```

Try it online!

### Explanation

```
          a & b are command-line args (implicit)
   aX     String-multiply the digit by each number in...
     \,b  inclusive range from 1 through the number of terms
  Y       Yank (to enforce desired precedence)
$+        Fold on addition
          Autoprint (implicit)

```

# Answer
> 1 votes
# Java (JDK), 53 bytes

```
x->n->{int r=0,y=0;for(;n-->0;)r+=y=y*10+x;return r;}

```

Try it online!

# Answer
> 0 votes
# Ruby, 24 bytes

```
->x,n{(10**-~n/9-n)/9*x}

```

Try it online!

Stole the formula from Wasif.

# Answer
> 0 votes
# Lua, 46 bytes

```
function f(x,n)return(10*10^n-10-9*n)/81*x end

```

Try it online!

-11 bytes thanks to @Delfad0r

# Answer
> 0 votes
# Charcoal, 9 bytes

```
Ｉ×Ｎ↨…·¹Ｎχ

```

Try it online! Link is to verbose version of code. Explanation: Port of @Bubbler's Jelly answer. This version takes `x` as the first input but it can be trivially modified to take `n` as the first input instead.

```
       Ｎ    `n` as a number
    …·¹     Inclusive range starting at 1
   ↨    χ   Convert from "base 10"
 ×           Multiplied by
  Ｎ          `x` as a number
Ｉ            Cast to string
             Implicitly print

```

By comparison, using string repetition would also take 9 bytes, even if Charcoal supported vectorised string repetition (it doesn't).

# Answer
> 0 votes
# Wolfram Language (Mathematica), 21 bytes

```
Tr[10^Range@#2-1]/9#&

```

Try it online!

-5 bytes from @att

# Answer
> 0 votes
# Scala, 32 bytes

```
x=>1.to(_).map(x.*(_).toInt).sum

```

Try it in Scastie!

I ain't using any of those newfangled formulas! Accepts x as a string, then n as an `Int`.

# Answer
> 0 votes
# MMIX, 32 bytes (8 instrs)

```
00000000: e302 0000 e3ff 0000 2aff ffff 28ff ff00  ẉ£¡¡ẉ”¡¡*”””(””¡
00000010: 2202 02ff 2701 0101 5b01 fffc f803 0000  "££”'¢¢¢[¢”‘ẏ¤¡¡

```

```
wrd SET   $2,0              // s = 0
    SET   $255,0            // t = 0
0H  4ADDU $255,$255,$255
    2ADDU $255,$255,$0      // loop: t = t * 10 + x
    ADDU  $2,$2,$255        // s += t
    SUBU  $1,$1,1
    PBNZ  $1,0B             // if(--n) goto loop
    POP   3,0               // return s

```

# Answer
> 0 votes
# cQuents, 10 bytes

```
;Z+At^($-1

```

Try it online!

# Answer
> 0 votes
# Pyth, 6 bytes

```
sms*wh

```

Try it here!

Uses some... creative input trickery. Notice that the problem is a special case of \\$\sum\_{j=0}^{n-1}\sum\_{i=0}^jx\_j\cdot10^{i\cdot(\lfloor\log\_{10}(x\_j)\rfloor+1)}\\$, where all \\$x\_i\\$ are equal (\\$x\\$) and \\$x\in\mathbb Z,0\le x\le9\\$. This solution solves the nonnegative integer case, and takes input as \\$n\\$, followed by \\$x\\$ \\$n\\$ times. For example, for \\$x=6,n=2\\$, the input is:

```
2
6
6

```

If \\$x\\$ must only be input once, the solution is 8 bytes ~~and much more boring~~.

---
Tags: code-golf, math, sequence
---


# Question
Title: Find the magic numbers to divide a number without division
An integer \\$x\in\[0,2^{32}-1\]\\$ divided by an integer \\$d\in{\[1,2^{31}\]}\\$ will produce an integral quotient \\$q\\$ and a remainder \\$r\\$, so that \\$x=d\times q+r\\$.

Any \\$q\\$, in fact, can be calculated by the following formula.

$$y=\left\lfloor\frac{mx}{2^{32}}\right\rfloor\\q=\left\lfloor\frac{y+f\lfloor(x-y)/2\rfloor}{2^s}\right\rfloor$$

where

$$m,s,f\in Integer\\m\in\[2,2^{32}\]\\s\in\[0,31\]\\f\in\\{0,1\\}$$

The formula can be rewritten with bitwise operators, to be more friendly with computers.

$$y=mx\gg32\\q=y+(x-y\gg1\ \\&\ {-f})\gg s$$

Given \\$d\\$, produce a valid tuple \\$(m,s,f)\\$, so that applying the formula above will compute the correct value of \\$q\\$ for all \\$x\\$.

There may be multiple valid solutions, in which case you can output any number of any valid solution.

---

### Test Cases

```
(d -> m, s, f)
1 -> 4294967296, 0, 0
2 -> 2147483648, 0, 0
3 -> 2863311531, 1, 0
7 -> 613566757, 2, 1
11 -> 3123612579, 3, 0
111 -> 657787785, 6, 1
1111 -> 989659431, 8, 0
11111 -> 2038283013, 13, 1
1111111111 -> 2075258709, 29, 0
2147483647 -> 3, 30, 1
2147483648 -> 2, 0, 0

```

Each of the listed output is not the only possible solution. For example, both of these are correct.

```
1111111111 -> 2075258709, 29, 0
1111111111 -> 4150517417, 30, 0

```

# Answer
> 8 votes
# Python 3.8 (pre-release), 271 bytes

```
lambda d,P=2**32:[s:=min(range(32),key=lambda n:abs(ceil((P<<n)/d)*d-(P<<n))),m:=ceil((P<<s)/d),0]*(1<m<=P and m*d>>(32+s))or[s:=min([n for n in range(32)if 1<2**(33+n)/d-P<=P],key=lambda n:abs(ceil(2**(33+n)/d)*d-(2*P<<n))),m:=floor(2**(33+s)/d+1)-P,1]
from math import*

```

Try it online!

Probably severely golfable.

Returns a list of three elements in the order `[s, m, f]`.

Here is a calculator that uses my function. You input a Python division expression (`dividend/divisor`), and it uses my function to return a quotient without directly dividing the dividend by the divisor.

Thanks @pxeger for suggesting the use of bitwise operators (`2**(32+s)` -\> `P<<s`) in some places, which saves ten bytes.

## Explanation

The problem can be solved by comparing the "magic quotient" expression to the actual quotient. Since `f` is either zero or one, we can split the problem into two parts.

If f is zero, then the "magic quotient" expression becomes:

$$\left\lfloor \frac{y}{2^s} \right\rfloor = \left\lfloor \frac{\left\lfloor \frac{mx}{2^{32}} \right\rfloor}{2^s} \right\rfloor$$

We can ignore the floor functions so that the problem becomes one of approximation rather than complete accuracy. Then, the magic quotient becomes:

$$\frac{mx}{2^{32+s}}$$

What we want to do is find \\$m\\$ and \\$s\\$ such that the value above most closely approximates \\$\frac{x}{d}\\$. We want

$$\frac{mx}{2^{32+s}} \approx \frac{x}{d} \implies mdx \approx x2^{32+s} \implies md \approx 2^{32+s}$$

This problem is a lot easier to solve than the daunting task of dealing with floors and correcting errors, or, even worse, dealing with those pesky fractions. In fact, this part is very simple. We can just loop through the 32 possible values of \\$s\\$ and find the one with the lowest

$$\left\lceil \frac{2^{32+s}}{d} \right\rceil \times d - 2^{32+s}$$

We use the ceiling, and not the floor, because later on we use the floor to compute the quotient, and the ceiling allows us to get a more precise value.

The above expression is evaluated for each \\$s\\$ from 0 to 31, and the \\$s\\$ for which that expression is the lowest is the one that is to be outputted (or is at least considered for output). Next, we evaluate \\$m\\$, which is the ceiling expression above.

Then \\$f\\$ is zero (assumed above).

Now, of course, \\$f\\$ cannot always be zero, so some checks are done to determine whether or not \\$f = 0\\$ in fact works. \\$f = 0\\$ works if:

* \\$m\\$ is within the required range; and
* the magic quotient of \\$d\\$ by \\$d\\$ is equal to one (if it isn't, then we need some additional value in the numerator, which is where \\$f = 1\\$ comes in).

The second condition is sufficient because, considering some nonnegative integer \\$ad+b\\$ where \\$a\\$ and \\$b\\$ are nonnegative integers, \\$b\\$ being less than \\$d\\$, the value of

$$\left\lfloor \frac{\left\lfloor \frac{mad+mb}{2^{32}} \right\rfloor}{2^s} \right\rfloor = \left\lfloor \frac{\left\lfloor \frac{amd}{2^{32}} \right\rfloor}{2^s} \right\rfloor$$

This is because \\$mb\\$ is less than \\$md\\$, so \\$\frac{mb}{2^{32}}\\$ is less than one.

If the magic quotient of \\$d\\$ by \\$d\\$ is one, then

$$\left\lfloor \frac{\left\lfloor \frac{md}{2^{32}} \right\rfloor}{2^s} \right\rfloor = 1$$

Consequently,

$$\left\lfloor \frac{\left\lfloor \frac{amd}{2^{32}} \right\rfloor}{2^s} \right\rfloor = a \left\lfloor \frac{\left\lfloor \frac{md}{2^{32}} \right\rfloor}{2^s} \right\rfloor = a$$

which is indeed the integer part of \\$\frac{ad+b}{d}\\$. Since this works for every \\$ad+b\\$, the \\$s\\$, \\$m\\$ and \\$f\\$ values are satisfactory.

Otherwise, we need to consider \\$f = 1\\$. This value of \\$f\\$ will definitely work.

The problem is more complicated if \\$f = 1\\$, but it is still a problem of approximation. I'll leave the work of finding the simple equation to you, but here it is for those who don't have the time / are too lazy to do the work themselves:

$$d(m+2^{32}) \approx 2^{33+s}$$

From here, the work is very similar to before, except that since we **must** get a good value, we restrict the search space to the values of \\$s\\$ such that the \\$m\\$ corresponding to \\$s\\$ is within the required range. Another difference is that \\$m\\$ is found using a Python equivalent of `-~` rather than `ceil`, the difference between them being that `-~` increments integers whereas `ceil` leaves them unchanged. I'm still unsure as to why this is needed, but it works so I'm not going to question it.

I don't do these long mathematical explanations very often, so feel free to critique my mathematics. If the LaTEX looks weird, please do tell me so I can fix it. My reasoning might also be wrong, so if it is, please tell me.

# Answer
> 4 votes
# Charcoal, ~~64~~ 61 bytes

```
Ｎθ≔Ｘ²¦³²η≔⌕ＥＸ²…³²¦⁶⁴÷×⁻⊖η﹪ηθ﹪±ιθι⁰ζ≔÷×ηＸ²ζθε≔›εηδＩ⟦⁻ε×δ⊖η⁻ζδδ

```

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

```
Ｎθ

```

Input `d`.

```
≔Ｘ²¦³²η

```

Precompute `2³²` as it gets used several times.

```
≔⌕ＥＸ²…³²¦⁶⁴÷×⁻⊖η﹪ηθ﹪±ιθι⁰ζ

```

Find the first power of `2` between `2³²` and `2⁶⁴` which satisfies the formula in `A346496`, even if `d` is a power of `2`. Note that the formula given there calculates the first `b` where `2**b<=(2**32-(2**32%d)-1)*(d-1-(2**b-1)%d)`, but I actually calculate `(2**32-(2**32%d)-1)*(-2**b%d)//(2**b)` and find the first `b` where that is `0`. For now, assume `f=0` and `s=b-32`.

```
≔÷×ηＸ²ζθε

```

Assume `m=A346495(d)` (but using the value of `b` computed above even if `d` is a power of `2`). This value is correct if it lies within the desired range `[2..2³²]`.

```
≔›εηδ

```

Compute `f=m>2³²`.

```
Ｉ⟦⁻ε×δ⊖η⁻ζδδ

```

If `f=1`, subtract `2³²-1` from `m` and `1` from `s`. (The OEIS algorithm for `m>2³²` seems to erroneously hard-code the value of `s-1` as `2`, which happens to work for its example of `d=7`.) Output the final values of `m`, `s` and `f`.

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


# Question
Title: Pairs of integers ordered by their exponentiation
Output the infinite list of pairs of integers `(a, b)`, where both \\$ a \> 1 \\$ and \\$ b \> 1 \\$, ordered by the value of \\$ a^b \\$. When there are multiple pairs where \\$ a^b \\$ is equal, they should be ordered lexicographically.

For example, \\$ 2^4 = 4^2 = 16 \\$, but `(2, 4)` should come before `(4, 2)`, because it is lexicographically earlier.

This sequence starts:

```
2, 2
2, 3
3, 2
2, 4
4, 2
5, 2
3, 3
2, 5
6, 2
7, 2

```

Here are the first 100,000 pairs: https://gist.github.com/pxeger/0974c59c38ce78a632701535181ccab4

## Rules

* As with standard challenges, you may choose to either:
    + Take an input \\$ n \\$ and output the \\$ n \\$th pair in the sequence
    + Take an input \\$ n \\$ and output the first \\$ n \\$ pairs
    + Output the sequence indefinitely, e.g. using a generator
* You may use \\$ 0 \\$\- or \\$ 1 \\$-indexing
* You may use any standard I/O method
* Standard loopholes are forbidden
* This is , so the shortest code in bytes wins

# Answer
# Brachylog (v2), 12 bytes

```
⟦+₂ᵐgj∋ᵐ.^?∧

```

Try it online!

Function submission, a generator that generates all solutions. The TIO link uses a header + a command-line argument to print the first ten.

## Explanation

```
⟦+₂ᵐgj∋ᵐ.^?∧
⟦              Form a range from 0 to ? inclusive, for some number ?
 +₂            Add 2 to
   ᵐ             each element of the range
     j         Make two copies of the range
    g            as two separate lists (don't concatenate them)
      ∋        Generate all ways to select one element
       ᵐ         from each list
         ^       such that the first element to the power of the second
          ?      is ?
        .  ∧   and output the selected elements

```

Not *explicitly* specified is the ordering, but  will try possible values of `?` in order (which in this case are positive integers), and  will process the first element before the second (so it'll try 2⁴ before 4² because it's checking all possible exponents with base 2, then all possible exponents with base 3, etc.)

This algorithm is, of course, very inefficient. A reversed exponentiation, `~^`, seems like it could be an efficient way to solve the problem, and potentially shorter too – but adding the requirement that the base and exponent are ≥2 is nontrivial when writing the program in that form, and more importantly, Brachylog seems to enter an infinite loop when trying to calculate what value the base and exponent have in that situation. So the Jelly-ish algorithm written here is probably the best available option in the current version of Brachylog.
> 6 votes

# Answer
# JavaScript (V8), 58 bytes

```
for(i=3;k=++i;)for(j=1;k=k<i?k:j++<i;)j**++k-i||print(j,k)

```

Try it online!

Outputs indefinitely.

This code is shorter than it would be were I to remove the third for-loop and instead use logarithms.

Thanks to @Arnauld for -2 bytes and to @tsh for -2 more.
> 5 votes

# Answer
# Vyxal, 9 bytes

```
ɾ›:Ẋµƒe;Ẏ

```

Try it Online!

```
ɾ›        # 2..n+1
  :Ẋ      # Cartesian product with self
    µ  ;  # Sort by...
     ƒ    # Reduce by...
      e   # Exponentiation.
        Ẏ # Get the first n.

```
> 5 votes

# Answer
# Ruby, ~~70 60~~ 52 bytes

```
2.step{|x|x.times{|y|x.times{|z|x==y**z&&p([y,z])}}}

```

Try it online!

### How actually?

For any given x (starting from 2), check if there is a pair of values y,z in the range (0,x-1) which satisfies y^z==x

y and z will be greater than 2 because:

* If z==0, the result will be 1
* If y==0, the result will be 0 (or 1)
* If y==1, the result will be 1
* If z==1, the result will be y, which is always less than x
> 5 votes

# Answer
# Python 3.8 (pre-release), ~~75~~ 67 bytes

*Thanks @pxeger for -8 bytes*

```
i,=r=2,
while[j**k-i or print(j,k)for j in r for k in r]:i+=1;r+=i,

```

Try it online!

Prints indefinitely.

Port of @ophact's Javascript answer. Can probably still be golfed considerably, cuz I'm a noob at golfing in Python :P
> 4 votes

# Answer
# Jelly, 10 bytes

```
‘Ḋ*þ`ZŒỤ‘ḣ

```

Try it online!

This works either as a full program or as a function. Takes an argument *n* and returns the first *n* pairs.

## Explanation

```
‘Ḋ*þ`ZŒỤ‘ḣ
 Ḋ            Form an inclusive range from 2 to
‘               {n} + 1
   þ          Form an                table
  *                   exponentiation
    `           using {that range} and itself
     Z        Transpose (so that (x+1)^(y+1) is at index [x,y])
      ŒỤ      Produce a list of all coordinates (index pairs) in
                {the table}, sorted by the values of the table
        ‘     Increment {both halves of each coordinate pair}
         ḣ    {Output} the first {n} {coordinate pairs}

```

The basic idea is that given an input *n*, we calculate all possible exponentiations of numbers in the range 2 to *n*+1 inclusive, then return the inputs that produced the *n* lowest results. Jelly's tiebreak for `ŒỤ` happens to match the tiebreaking behaviour required by the question, but we need to transpose the table (and add 1 to the coordinates – Jelly uses 1-based coordinates but the exponentiation table conceptually uses 2-based coordinates) to make the coordinate system also match the format required by the question.

The range 2 to *n*+1 is sufficient because any *x**y* which is out of this range would have to be larger than 22 … 2*n*+1 or than 22 … (*n*+1)2, i.e. larger than *n* different elements, so it can't appear in the portion of the sequence we're outputting.
> 4 votes

# Answer
# , ~~26~~ 23 bytes

Returns the first n pairs.

```
{.&(/:^/&>)&,[:{@;~2+i.

```

Try it online!

`2+i.` Integers from 2 to n+1.
`{@;~` Table of all pairs of these integers.
`(/:^/&>)&,` Flatten into a list of pairs and sort by the value of the exponentiation.
`{.` Take the first n pairs.
> 4 votes

# Answer
# 05AB1E, 9 bytes

```
L>ãΣ`m}I£

```

Outputs the first \\$n\\$ pairs.

Port of *@emanresuA*'s Vyxal answer.

Try it online.

Could alternatively be the 1-based \\$n^{th}\\$ value by replacing `£` with `è`: try it online.
The infinite sequence would be 2 bytes longer: `∞εL>ãΣ`m}Nè` \- try it online.

**Explanation:**

```
L       # Push a list in the range [1, (implicit) input]
 >      # Increase each by 1 to make the range [2,input+1]
  ã     # Pop and push the cartesian product of itself to get all pairs
   Σ    # Sort this list of pairs by:
    `   #  Pop and push both values separated to the stack
     m  #  Exponentiation
   }I£  # After the sort-by: leave the first input amount of pairs
        # (which is output implicitly as result)

```
> 3 votes

# Answer
# Python 2, ~~75~~ 76 bytes

Outputs the first `n` pairs. (A previous version of this answer was one byte shorter by returning just the `n`th pair, but it raised an error for n \<= 2.)

Not as short as @Aidan Chow's Python answer, but I wanted to see how well `sorted` would do. Using Python 2's lambda argument destructuring is a bit shorter than `lambda p:p[0]**p[1]` in Python 3.

```
lambda n:sorted([(i/n+2,i%n+2)for i in range(n*n)],key=lambda(i,j):i**j)[:n]

```

Try it online!
> 3 votes

# Answer
# Jelly, 7 bytes

```
p`‘*/Þḣ

```

Try it online!

Port of my Vyxal. -1 thanks to ovs.

```
p`       Cartesian product with (implicit) range from 1 to self
  ‘      Increment anything
     Þ   Sort by...
    /    Reduce by...
   *     Exponentiation
      ḣ  Get first n.

```
> 2 votes

# Answer
# , ~~57~~ ~~55~~ ~~50~~ 46 bytes

```
\(n)cbind(a<-n:1+1,b<-a%x%!!a)[order(a^b)[n],]
```

Attempt This Online!

Returns the \\$n^\text{th}\\$ value.

-2 bytes thanks to pajonk, then -4 more bytes thanks to pajonk. -1 byte thanks to Dominic van Essen.
> 2 votes

# Answer
# Haskell, 45 bytes

```
f=[(y,z)|x<-[2..],y<-[2..x],z<-[2..x],y^z==x]

```

Try it online!

*f* is the infinite sequence.

Inspired by @G B answer
> 2 votes

# Answer
# APL+WIN, 27 bytes

Prompts for desired term i.

```
(v[⍋*/¨v←,n∘.,n←1+⍳i])[i←⎕]

```

Try it online! thanks to Dyalog APL Classic
> 1 votes

# Answer
# Charcoal, 41 bytes

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

```

Try it online! Link is to verbose version of code. Outputs the first `n` terms. Explanation: Inspired by @ais523's answer.

```
Ｎθ

```

Input `n`.

```
ＦθＦθ⊞υ⟦Ｘ⁺²ι⁺²κ⁺²ι⁺²κ⟧

```

Generate the Cartesian product of `[2..n+2)` with itself, plus include the result of the exponentiation as the first term.

```
≔⟦⟧ηＦθ⊞η⌊⁻υη

```

Get the `n` lowest terms from that list, which takes values in ascending order of exponentiation resolving ties by taking the base in ascending order.

```
ＩＥη✂ι¹

```

Output the terms but exclude the exponentiations.

35 bytes using the newer version of Charcoal on ATO:

```
ＮθＦθ⊞υ⌊⁻ΣＥθＥθ⟦Ｘ⁺²κ⁺²μ⁺²κ⁺²μ⟧υＩＥυ✂ι¹

```

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

# Answer
# Java 8, 91 bytes

```
n->{for(int t=4,i;;t++)for(i=1;i++<t*t;)if(Math.pow(i/t,i%t)==t&&--n<0)return i/t+","+i%t;}

```

Outputs the 0-based \\$n^{th}\\$ value.

Try it online.

Outputting the infinite sequence is 6 bytes longer:

```
n->{for(int t=4,i;;t++)for(i=1;i++<t*t;)if(Math.pow(i/t,i%t)==t)System.out.println(i/t+","+i%t);}

```

Try it online

**Explanation:**

```
n->{                   // Method with integer parameter and String return-type
  for(int t=4,         //  Target-integer, starting at 4
          i;           //  Output integer, uninitialized
      ;                //  Loop indefinitely:
       t++)            //    Increase `t` by 1 after every iteration
    for(i=1;i++<t*t;)  //   Inner loop `i` in the range (1,t*t):
      if(Math.pow(i/t, //    If `i` integer-divided by `t`
                  i%t) //    to the power `i` modulo-`t`
          ==t&&        //    Is equal to `t`:
         --n           //     First decrease the input by 1
            <0)        //     And if it's now negative:
        return i/t+","+i%t;}
                       //      Return the divmod of `i,t` as result

```
> 1 votes

# Answer
# Julia 1.0, 49 bytes

```
!n=sort([a^b=>a=>b for a=2:n+1,b=2:n+1][:])[n][2]

```

Try it online!

output is the n-th pair in the sequence (1-indexed). For n\>14, a `BigInt` is expected to avoid overflow
> 1 votes

# Answer
# Retina, 98 bytes

```
.+
*
L$`_
$=$.($`__
%L$`_(?=_*(.+))
:$1,$.($`__
%~`:(.+),(.+)
^¶$$.($2*$($1$*
N`.+
"$+"+0`.+:

A`:

```

Try it online! Outputs the first `n` terms. Explanation: Port of my Charcoal answer inspired by @ais523's answer.

```
.+
*

```

Convert `n` to unary.

```
L$`_
$=$.($`__

```

Create the numbers from `2` to `n+1` in decimal, each prefixed with `n` in unary.

```
%L$`_(?=_*(.+))
:$1,$.($`__

```

Create the Cartesian product of the range `2` to `n+1` with itself.

```
%~`:(.+),(.+)
^¶$$.($2*$($1$*

```

Precede each product with its exponentiation, computed by constructing a repeated multiplication and evaluating it.

```
N`.+

```

Sort the exponentiations, resolving ties stably i.e. keeping the lowest base first.

```
"$+"+

```

Loop `n` times...

```
0`.+:

```

... delete one exponentiation.

```
A`:

```

Keep only the lines where the exponentiation was removed i.e. the first `n` lines.
> 1 votes

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


title: Rolling a ball over a list

text:
# Question
Title: Rolling a ball over a list
Starting with a binary list (just `1`s and `0`s) we are going to roll a ball over it. The ball has a position and a direction. At every step the ball does the following:

* If the number at it's position is `1`, then flip the direction. It "bounces".
* Flip the number, if it's `0` replace it with `1`, if it's `1` replace it with `0`.
* Move 1 step in the direction.

We start execution with the ball at the first position heading to the right. When the ball is out of the range of the list either to the left or the right we stop execution.

For an example here is each step being run with `[0,0,0,1,0]` to start.

```
[0,0,0,1,0]
 ^>
[1,0,0,1,0]
   ^>
[1,1,0,1,0]
     ^>
[1,1,1,1,0]
       ^>
[1,1,1,0,0]
    <^
[1,1,0,0,0]
       ^>
[1,1,0,1,0]
         ^>
[1,1,0,1,1]
           ^>

```

## Task

Given a starting list as input output the list after the ball has rolled over it.

This is the goal is to minimize the size of the source code as measured in bytes.

## Test cases

```
[0,0,0,0,0] -> [1,1,1,1,1]
[0,0,0,1,0] -> [1,1,0,1,1]
[0,0,1,1,0] -> [1,0,0,1,1]
[0,1,0,1,0] -> [0,1,0,1,1]
[1,1,1,1,1] -> [0,1,1,1,1]
[1,0,1,0,0] -> [0,0,1,0,0]
[0,1,0,1] -> [0,1,0,1]

```

# Answer
# tinylisp, ~~130~~ ~~118~~ 98 bytes

```
(load library
(d B(q((L R)(i R(i(h R)(reverse(B(c 0(t R))L))(B(c 1 L)(t R)))(reverse L
(q((L)(B()L

```

Try it online!

-12 bytes thanks to Razetime. See the edit history for a `library`-less version.

-20(!) bytes thanks to DLosc. Maybe I'm not very good at golfing in tinylisp...

`B` does the rolling.

```
(def roll_ball
  (lambda (Left Right Dir)				; takes left, right direction
    (if (equal? Dir 1)					; if direction is 1,
      (reverse (roll_ball Right Left 0))		; reverse the result of roll_ball with left and right lists flipped
      (if (nil? Right)					; if we're at the end of the list,
        (reverse Left)					; reverse the left list and return
        (if (equal? (head Right) 1)			; otherwise, if the head is 1
          (roll_ball Left (cons 0 (tail Right)) 1)	; recurse, flipping the direction and changing the first element of Right to 0
          (roll_ball (cons 1 Left) (tail Right) 0)	; otherwise, recurse on L, and add 1 to the Left
        )))))

```

# tinylisp, ~~69~~ 62 bytes

```
(load library
(d F(q((L)(i(h L)(c 0(t L))(concat(map not(t L))(q(1

```

Try it online!

Port of tsh's answer.
> 8 votes

# Answer
# x86-64 machine code, 19 bytes

```
6A 01 58 99 80 34 17 01 75 02 F7 D8 01 C2 39 F2 72 F2 C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI the address of an array of 8-bit integers and its length in RSI, and modifies it in place.

In assembly:

```
f:  push 1      # Push 1 onto the stack.
    pop rax     # Pop it into RAX.
    cdq         # Sign extend EAX into EDX, making EDX 0.
                    # EDX will hold the current index into the array
                    #  and EAX will hold the current direction (±1).
r:  xor BYTE PTR [rdi+rdx], 1   # Flip the current number.
    jnz s           # Jump if the new value is not 0.
    neg eax         #  Otherwise, the old value was 1; invert the direction.
s:  add edx, eax    # Advance in the current direction.
    cmp edx, esi    # Compare the current index with the length.
    jb r            # Jump back if the index is lesser, as unsigned integers;
                    #  this will stop if it goes off either end,
                    #  equaling the length or overflowing to all 1s.
    ret             # Return.

```
> 7 votes

# Answer
# JavaScript (Node.js), 36 bytes

```
i=>i.map((n,j)=>i[0]?j>0&n:i[j+1]^1)

```

Try it online!

I don't have any proof of its correctness. It just passed all testcases. So it works.
> 7 votes

# Answer
# , ~~69~~ ~~68~~ 66 bytes

Or **\>=4.1, 59 bytes** by replacing the word `function` with a `\`.

*Edit: -1 byte thanks to @Giuseppe.*

```
function(v,a=0){while((F=F+(T=(-T)^a))&&!is.na(a<-v[F]))v[F]=!a;v}

```

Try it online!

The `T=(-T)^a` trick abuses the fact that going left may only last for one step.

---

# , 41 bytes

Or **\>=4.1, 34 bytes** by replacing the word `function` with a `\`.

```
function(v)"if"(v,c(0,v[-1]),c(!v[-1],1))

```

Try it online!

Port of @tsh'sanswer (with explanation by @Jonah).
> 5 votes

# Answer
# , 18 bytes

```
{.{(1-0,~}.),:0,}.

```

Try it online!

Based on tsh's JS answer.

## how

* `{.{...,:...` If the input begins with 1...
* `0,}.` Change the 1 to a 0 (we're just bouncing off the first element and halting)
* `1-0,~}.` Otherwise, remove the first element, append a 0, and then, for each element, return the opposite of its right neighbor.

## why does this work?

This is an induction argument suggested by alephalpha in the comments of tsh's answer.

* Consider the 1 element case. Clearly, a 1 becomes 0 and a 0 becomes 1. Also note that in the 0 case we're traveling right when we halt, and in the 1 case we're traveling left. Let's go ahead and add "begins with 0 exits right" to our induction hypothesis.
* Assuming the hypothesis, consider the two cases:
    + `1 [n element input]` Clearly true as we bounce off first element.
    + `0 [n element input]` We now consider the two cases for the `n element input`:

    ```
    Begins with 1:
    >
    0 1 ...
      >
    1 1 ...
    <
    1 0 ...
      >
    0 0 ... By induction, this will exit right,
            so the initial element is proven 0, as needed.

    Begins with 0:
    >
    0 0 ...
      >
    1 0 ... By induction, this will exit right,
            so the initial element is proven 1, as needed.

    ```
> 5 votes

# Answer
# Python 3, 57 bytes

*-13 bytes thanks to `Wheat Wizard`, -5 thanks to `ophact`, -2 thanks to `loopy walt` and -1 thanks to `pxeger`*

```
def f(x):
 i=c=0
 while-~i*x[i:]:c^=x[i];x[i]^=1;i+=1-2*c

```

Try it online!
> 4 votes

# Answer
# Brain-Flak, 90 bytes

```
(([]){(){}((()[{}])<{{}(<>)}{}>)<>([])}()){({}({})([{}()]))}{}{{}<>([]){{}({}<>)<>([])}}<>

```

Try it online!

36 bytes to simulate the ball rolling, and 54 to ensure that the input is in the right direction.
> 3 votes

# Answer
# Python 3, 84 bytes

Not a great score, but somewhat interesting.

This takes a list of bits encoded as an integer and a length argument and outputs a new list of bits encoded as an integer. It’s a literal implementation, not induction based.

Improvements are welcome, I haven’t gotten any of my attempts to make it smaller working. Maybe c would be a better language to port this answer to.

Thanks to pxeger for -5!

```
def f(x,l,b=1,d=1):
 a=1<<l;c=a>>b;d*=x&c<1or-1
 return f(x^c,l,b+d,d)if c&a-1else x

```

Try it online!
> 3 votes

# Answer
# JavaScript (Node.js), 55 bytes

```
f=(n,d=1,a=0,C=n[a])=>C<2?f((n[a]^=1,n),d=C?-d:d,a+d):n

```

Try it online!
> 2 votes

# Answer
# C (gcc), ~~59~~ 58 bytes

```
f(a,l)int*a;{for(int i=0,d=1;i<l+0u;)i+=d*=(a[i]^=1)*2-1;}

```

Try it online!

-1 thanks to l4m2, making the numbers unsigned for the bounds check.
> 2 votes

# Answer
# 05AB1E, 24 bytes

```
[ā<¾å_#D¾è©_¾ǝ®XαDUi¼ë.¼

```

Try it online or verify all test cases.

**Explanation:**

```
[           # Start an infinite loop:
 ā<         #  Push a list in the range [0,length) (without popping the list)
            #  (which will use the implicit input-list in the first iteration)
   ¾å_      #  If this list does not contain value `¾` (so we're out of bounds):
            #  (`¾` is 0 by default)
      #     #   Stop the infinite loop
 D          #  Duplicate the current list
  ¾è        #  Get the value at index `¾`
    ©       #  Store it in variable `®` (without popping)
     _      #  Invert the bit (with an ==0 check)
      ¾ǝ    #  Insert it back into the list at the same position `¾`
  ®Xα       #  Get the absolute difference between `®` and `X`
            #  (`X` is 1 by default)
     DU     #  Store this as new value `X`
       i    #  If this absolute difference `X` is 1:
        ¼   #   Increment `¾` by 1
       ë    #  Else:
        .¼  #   Decrement `¾` by 1 instead
            # (after which the list is output implicitly as result)

```
> 2 votes

# Answer
# Retina 0.8.2, ~~35~~ 24 bytes

```
1T`d`10`0.*|1
^1(.*)
$+1

```

Try it online! Link includes test cases. Explanation: Uses @tsh's method (see @Jonah's explanation).

```
1T`d`10`0.*|1

```

Invert the first bits, or all of the bits if the first bit is a `0`.

```
^1(.*)
$+1

```

If the first bit is now a `1` then move it to the end.

Previous 35-byte version actually performed the steps given in the question:

```
^
>
{`>0
1>
>1
<0
0<
<1
}`1<
0>
\D

```

Try it online! Link includes test cases. Explanation:

```
^
>

```

Mark the initial position and direction of the ball.

```
{`
}`

```

Repeat until the ball goes out of range.

```
>0
1>
>1
<0
0<
<1
1<
0>

```

Flip the number at the current position and update the position and direction of the ball. (I don't know any shorter way of describing this in Retina; even `T`>1<`<0>`>1|1<` is three bytes longer than replacing `>1` and `<1` manually.)

```
\D

```

Delete the marker.
> 2 votes

# Answer
# JavaScript (ES6), 48 bytes

```
f=(a,d,i=0)=>1/a[i]?f(a,d^=!(a[i]^=1),i+1-2*d):a

```

Try it online!
> 2 votes

# Answer
# Wolfram Language (Mathematica), 33 bytes

```
If[#>0,{0,##2},1-{##2,0},{}]&@@#&

```

Try it online!

A port of @tsh's JavaScript answer.
> 2 votes

# Answer
# Jelly, 7 bytes

```
Ż¬;1ƊḢ?

```

Try it online!

Port of Jonah's excellent J solution.

```
     Ḣ     Remove the first element of the input.
Ż     ?    If it's 1, prepend 0 to the remaining elements, else
 ¬         negate the remaining elements
  ;1Ɗ      and append a 1.

```
> 2 votes

# Answer
# Jelly, 7 bytes

```
ḢCɓŻṙ⁹^

```

Try it online!

Another port of tsh's idea:

```
ḢC         h = 1 - input.pop(0)
  ɓŻ       input.prepend(0)
    ṙ⁹          .rotate_left(h)
      ^         .xor(h)

```

I've rearranged it a bunch of ways looking for a 6-byte formulation, but I can't find one.

In J, this is something like `{.(-.@[|.=)0,}.` (15 bytes).
> 2 votes

# Answer
# Pari/GP, 49 bytes

```
a->i=d=1;while(i>0&&i<=#a,i+=d=-d+2*a[i]=!a[i]);a

```

Try it online!

---

## Pari/GP, 48 bytes, does not work for empty input

```
a->i=d=1;until(i<1||i>#a,i+=d=-d+2*a[i]=!a[i]);a

```

Try it online!

---

## Pari/GP, 44 bytes, does not work for empty input

```
a->if(a[1],a[1]=0;a,[!a[i%#a+1]|i<-[1..#a]])

```

Try it online!

A port of @tsh's JavaScript answer.
> 1 votes

# Answer
# Python 3, 172 bytes

```
d=1
c=0
l=[int(i)for i in input()]
while c>-1 and c<len(l):
    (d:=not(d))if(l[c]==1)else(d:=d)
    l[c]=not l[c]
    if d==1:
        c+=1
    else:
        c-=1
print(l)

```

I just passed all of the test cases

And if a bit gets changed, it becomes a boolean (False is 0 and True is 1)
> 1 votes

# Answer
# Charcoal, 18 bytes

```
Ｉ⎇§θ⁰Ｅθ∧κι⊞Ｏ⁻¹Φθκ¹

```

Try it online! Link is to verbose version of code. Explanation: Uses @tsh's method (see @Jonah's explanation).

```
   θ                Input array
  § ⁰               First element
 ⎇                  If nonzero then
      θ             Input array
     Ｅ              Map over elements
        κ           Current index
       ∧            Logical And
         ι          Current element
                    Else
             ¹      Literal integer `1`
            ⁻       Vectorised subtract
               θ    Input array
              Φ     Filtered by
                κ   Current index
          ⊞Ｏ     ¹  Append literal integer `1`
Ｉ                   Cast to string
                    Implicitly print

```
> 0 votes

---
Tags: code-golf, array
---


# Question
Title: The maximum liberty of a group on a Go board
## Bounty

One of the convincing conjectures, by Loopy Walt is,

```
maxlib(n) = 0, if n = 1
            2, if n = 2
            6, if n = 3
            (2n - 1)⌊n / 3⌋, if n % 3 = 0
            (2n - 1)⌊n / 3⌋ + n, if n % 3 = 2
            2n⌊n / 3⌋ + 1, otherwise

```

Loopy Walt's post below explains how this conjecture is derived, and contains a partial proof.

AnttiP and I will award 250 point bounty each to anyone who proves or disproves this conjecture.

I will award 50~500 point bounty for any other provable fast solution, depending on how fast it is.

### Introduction

The problem is about the game of Go. I will explain the basics you need to understand the problem, but if you are already familiar with this game, the problem is basically the following sentence.

*Compute the function \\$\operatorname{maxlib}(n)\\$ for a natural number \\$n\\$, whose output is the maximum number of liberties a group can have on an \\$n\times n\\$ Go board.*

\\$\operatorname{maxlib}(n)\\$ has an OEIS sequence (A320666). The currently known values is only up to \\$n=24\\$.

```
n maxlib(n)
1 0
2 2
3 6
4 9
5 14
6 22
7 29
8 38
9 51
10 61
11 74
12 92
13 105
14 122
15 145
16 161
17 182
18 210
19 229
20 254
21 287
22 309
23 338
24 376

```

Go is a board game played on an \\$n\times n\\$ square grid, with two players, black and white, placing a stone alternately on an empty intersection of the grid. In this challenge we will only consider the black stones (`X`).

On this \\$4\times4\\$ board, black has \\$3\\$ groups.

```
X X . .
X . X .
X X . X
. . X X

```

A *group* is a group of stones that are connected horizontally or vertically.

Let's denote each group with different alphabets.

```
A A . .
A . B .
A A . C
. . C C

```

Group `A` has \\$5\\$ liberties. Group `B` has \\$4\\$ liberties, and group `C` has \\$3\\$ liberties. *Liberty* is the number of empty spaces connected horizontally or vertically to a group.

```
. . .
. X .
. . .

. . .
X X .
. . .

. . .
X X X
. . .

```

There are three \\$3\times3\\$ boards each with a single black group. Counting the liberties, it is \\$4\\$, \\$5\\$, and \\$6\\$, respectively. In fact, on a \\$3\times3\\$ board with nothing else than \\$1\\$ black group, \\$6\\$ is the maximum number of liberties that group can have.

### Challenge

Compute the function \\$\operatorname{maxlib}(n)\\$ for a natural number \\$n\\$, whose output is the maximum number of liberties a group can have on an \\$n\times n\\$ Go board.

### Example Output up to \\$n=6\\$

```
X
1 -> 0

X .
. .
2 -> 2

. . .
X X X
. . .
3 -> 6

. . X .
. . X .
X X X .
. . . .
4 -> 9

. . . . .
. X X X X
. X . . .
. X X X .
. . . . .
5 -> 14

. X . . X .
. X . . X .
. X . . X .
. X . . X .
. X X X X .
. . . . . .
6 -> 22

```

You don't have to print the board positions.

### Scoring

I will run your program for 30 minutes on my computer, *not exclusively* on a single core. The maximum \\$n\\$ you can reach within this time is your score, starting from \\$n=1\\$ incrementing by \\$1\\$. Your program must reach at least \\$n=6\\$, and I will not run your program if this seems unlikely.

The maximum score you can get is 10000.

The OS is Linux, and here is my CPU information.

# Answer
> 7 votes
# Rust, score ≈ 15 in 37 minutes

This uses dynamic programming to run in \\$O((1 + \sqrt5)^n n^{3/2})\\$ time (much faster than a brute-force \\$2^{n^2}n^{O(1)}\\$ solution). The idea is that if we fill the grid row-by-row and column-by-column with stones or holes, trying each of these two decisions at each step, the only state we need to remember is

* whether the last point in each column has a stone or a hole,
* if it has a stone, which other stones it’s been connected to so far,
* if it has a hole, whether it’s already been counted as a liberty, and
* how many liberties have been counted so far;

and we can use a hash table to collapse states that are identical up to the number of counted liberties. The number of distinct states we need to store grows as \\$\frac{5(1 + \sqrt{5})^{n + 5/2}}{4\sqrt\[4\]{5}\sqrt{2\pi}n^{3/2}}\\$.

Build with `cargo build --release` and run with `cargo run --release`.

**`Cargo.toml`**

```
[package]
name = "liberty"
version = "0.1.0"
edition = "2021"

[dependencies]
mimalloc = { version = "0.1.28", default-features = false }

[profile.release]
codegen-units = 1
lto = true
panic = "abort"

```

**`src/main.rs`**

```
use mimalloc::MiMalloc;
use std::collections::HashMap;

#[global_allocator]
static GLOBAL: MiMalloc = MiMalloc;

#[derive(Copy, Clone, Eq, Hash, PartialEq)]
enum Point {
    Unused,
    Used,
    Stone(u32),
}

fn lib(n: usize) -> u32 {
    let mut states = HashMap::from([(vec![Point::Used; n], 0)]);

    let mut best = 0;

    for _i in 0..n {
        for j in 0..n {
            let mut states1 = HashMap::new();
            let mut add = |state: Vec<Point>, count: u32| {
                states1
                    .entry(state)
                    .and_modify(|c| *c = count.max(*c))
                    .or_insert(count);
            };
            for (state, count) in states {
                if state[j] != Point::Stone(j as u32) {
                    let mut state = state.clone();
                    let used = matches!(state[j], Point::Stone(_))
                        || (j != 0 && matches!(state[j - 1], Point::Stone(_)));
                    state[j] = if used { Point::Used } else { Point::Unused };
                    add(state, count + used as u32);
                } else if let Some(k) = state[j + 1..]
                    .iter()
                    .position(|&point| point == Point::Stone(j as u32))
                    .map(|k| j + 1 + k)
                {
                    let mut state = state.clone();
                    for point in &mut state[k..] {
                        if *point == Point::Stone(j as u32) {
                            *point = Point::Stone(k as u32);
                        }
                    }
                    state[j] = Point::Used;
                    add(state, count + 1);
                } else if !state[..j]
                    .iter()
                    .chain(&state[j + 1..])
                    .any(|state| matches!(state, Point::Stone(_)))
                {
                    best = best.max(count);
                }

                let mut state = state;
                let used0 = state[j] == Point::Unused;
                let used1 = j != 0 && state[j - 1] == Point::Unused;
                if used1 {
                    state[j - 1] = Point::Used;
                }
                if let Some(Point::Stone(k)) = j.checked_sub(1).map(|j1| state[j1]) {
                    if let Point::Stone(l) = state[j] {
                        if l < k {
                            for point in &mut state[k as usize..j] {
                                if *point == Point::Stone(k) {
                                    *point = Point::Stone(l);
                                }
                            }
                        } else if l > k {
                            for point in &mut state[j..] {
                                if *point == Point::Stone(l) {
                                    *point = Point::Stone(k);
                                }
                            }
                        }
                    } else {
                        state[j] = Point::Stone(k);
                    }
                } else if let Point::Stone(_) = state[j] {
                } else {
                    state[j] = Point::Stone(j as u32);
                }
                add(state, count + used0 as u32 + used1 as u32);
            }
            states = states1;
        }
    }

    for (state, count) in states {
        let mut it = state.into_iter();
        if let Some(j) = it.find_map(|point| {
            if let Point::Stone(j) = point {
                Some(j)
            } else {
                None
            }
        }) {
            if it.all(|point| {
                if let Point::Stone(k) = point {
                    j == k
                } else {
                    true
                }
            }) {
                best = best.max(count);
            }
        }
    }

    best
}

fn main() {
    for n in 0.. {
        println!("{n} {}", lib(n));
    }
}

```

# Answer
> 2 votes
# Python 3, Using pnlwc (Probably Definitely not loopy Walt's conjecture)

```
def pnlwc(n):
    if n<4:return[0,0,2,6][n]
    if n%3==0:return n//3*(2*n-1)
    if n%3==2:return n//3*(2*n-1)+n
    return n//3*2*n+1

```

Try it online!

## Conjectured optimal group

The conjectured formula seems to hold for all test cases larger than 3. It is definitely a lower bound, see the corresponding groups below.

n = 0 mod 3

```
............
XXXXXXXXXXXX
.X..X..X..X.
.X..X..X..X.
.X..X..X..X.
.X..X..X..X.
.X..X..X..X.
.X..X..X..X.
.X..X..X..X.
.X..X..X..X.
.X..X..X..X.
.X..X..X..X.

```

n = 2 mod 3

```
...........
XXXXXXXXXXX
.X..X..X..X
.X..X..X..X
.X..X..X..X
.X..X..X..X
.X..X..X..X
.X..X..X..X
.X..X..X..X
.X..X..X..X
.X..X..X..X

```

n = 1 mod 3

```
..........
XXXXXXXXXX
.X..X..X..
.X..X..X..
.X..X..XXX
.X..X..X..
.X..X..X..
.X..X..XXX
.X..X..X..
.X..X..XX.

```

### Partial proof:

*The n=0 mod 3 case is actually comparatively easy to prove:*

Start with a few easy observations:

1. We can assume that all squares are either stone or lib. Proof: (easy) exercise. Hint: trade squares that are neither against adjacent libs.
2. As a consequence, we can either maximise libs or minimise stones.
3. Another consequence is that each of the four corners must neighbour at least one stone. It follows that at least one pair of opposite edges (E and W, say) must be connected by a stone path.
4. (Arithmetic 101:) (a) the stone-to-lib ratio is at least 1:2. Indeed, the E-W path if it is straight has exactly this ratio. If it meanders, (b) each turn knocks off one lib. (c) 3-way (4-way) branch points knock off 3 (6) libs. (d) Ends gain 1 lib if in the open and are neutral at a wall. In either case they incur a net loss because they necessitate a branch point. Finally, (e) a straight hugging a wall or (f) running parallel to another straight less than 2 squares away loses 1 lib per length unit (2 if parallel and directly touching).

Note: the reader is encouraged to verify themselves that the group can indeed be thought of as assembled from connected horizontal and vertical straights.

Inspecting the claimed optimal pattern we see that it has no turns and exactly n/3 3-way branch points. It has n/3 x (n+1) stones and n/3 x (2n-1) libs which is as predicted by our arithmetic 101 exactly n short of doubling the stones.

We will now show that this is as good as it gets:

The group must contain either at least n/3 horizontal or at least n/3 vertical straights. If it doesn't there is a y coordinate y0 where there is no stone or lib caused by a horizontal straight and similar for x coordinates and vertical straights. But this would mean square y0,x0 is neither stone nor lib which we have ruled out.

Let's say WLOG that it is n/3 verticals. Generally, connecting k horz displaced vert straights will cost at the very least 2xk-2 libs as all but 2 vert straights must connect to at least two others each. Indeed, the cheapest way would be through two horz straights each connected via a turn to either end of the vert.

That does, however, not work for the case at hand because the horizontal ends of this construction do not line up flush (cf. fig) and there is not enough slack in the system to create compensating elements. For example, just pushing the bridging horz all the way to the wall costs too much (101.e).

```
. . . . . . . .
. . O O O O . .
O O X X X X O O
O O X O O X O O
O O X O O X O O
O O X O O X O O
X X X O O X X X
O O O . . O O O
. . . . . . . .

```

The next cheapest way of joining is branching off from a single horz which costs exactly n libs and is in fact precisely what the reference pattern does.

Note 1: This argument does not work for n=3 which may be viewed as a reason why the formula needs a special value there.

Note 2: The proof is relatively straight forward because for n=0 mod 3 the very small number of lost libs puts strong constraints on eligible patterns. The n=2 mod 3 and are considerably more forgiving and therefore tricky.

---
Tags: game, fastest-code, board-game, go
---


title: int, float or neither?

text:
# Question
Title: int, float or neither?
Given a string, determine if it is an int, a float or neither.

# Examples

* 123 - int
* 62727.0033 - float
* 644c.33 - neither

Your code should output a different value depending on which it is. For example it could return "i" for int, "f" for float and "n" for neither.

# Details

The following are floats:

```
1.00 -0.0 1.0

```

The following are not floats:

```
 1e3 1.0ec3 -1e3 1e-3 1e+3 --1.0 +1.0 NaN 1.0.0 1. .1 -001.1

```

The following are ints:

```
42 -2 -0

```

The following are not ints:

```
042 00

```

In short, the rule for floats is that it is a sequence of digits following by a `.` followed by a sequence of digits. Optionally `-` is prepended. If it starts with `0` then the `.` must follow directly afterwards.

The rule for ints is that it is a sequence of digits where the first digit is not `0`. The only exception is that `0` and `-0` are ints.

Either sort of number can have `-` optionally prepended to it.

You can assume the input will only contain printable-ASCII.

# Answer
# APL (Dyalog Unicode), ~~46~~ 39 bytes

Anonymous tacit prefix function. Returns 3 for float, 2 for int, and empty list for neither.

```
≢¨'^-?(0|[1-9]\d*)(\.\d+)?$'⎕S{⍵.Names}

```

Try it online!

**S**earches for the PCRE pattern `^-?(0|[1-9]\d*)(\.\d+)?$` then returns the name of the whole match and of each matched sub-pattern. Finally, the length of each (`≢¨`) list of names is returned. Since floats fill both sub-patterns, we get 3, while ints skip the last sub-pattern and thus give 2. Non-matches give an empty list.
> 5 votes

# Answer
# Python 3.8 (pre-release), 87 bytes

```
lambda s:"-if"[getattr(re.match(r'-?(0|[1-9]\d*)(\.\d+)?$',s),'lastindex',0)]
import re

```

Try it online!

Straight-forward regular expression. Python wrapper feels a bit clumsy, though.

Returns 'i','f' and '-'. If we are ok with 1,2 and 0 instead that would save 7 bytes.

Details:

`re.match` only matches at the beginning, no `^` required. Annoyingly, Python returns two different object types, depending on whether there is a match or not. To work around this we use the cumbersome `getattr` which allows us to specify a fallback for non existent attributes.
> 4 votes

# Answer
# Haskell, ~~95..~~ 61 bytes

```
f l=[1|(n,_)<-reads l,x<-["-0",show$round n],x==l||l==show n]

```

Try it online!

* As pointed out by @Peter Cordes there are floating point issues.
* Saved 18 Bytes by removing type hint to *reads* , thanks to @Unrelated String !
* Thanks to @Wheat Wizard for saving another 8 Bytes by applying *do notation*!
* Saved again 6 Bytes by @Wheat Wizard with a great use of list comprehension.

Returns:
*\[\]* = neither
*\[1\]* = Int
*\[1,1\]* = Float

We can return:
*""* = neither
*"1"* = Int
*"11"* = Float
By adding 2Bytes and building a \[Char\] list instead of \[Int\].
Or an integer 0,1 or 2 by applying sum to the result for +3

*f l* uses list comprehension conditional trick :
If *reads* finds a number then we use *(!)* to determine its type.
If it fails it return an empty list , hence list comprehension is empty.

*(!)* compares value found with input reconverting it to string

We sum to get a consistent value for *neither* , we would get 0 or empty list

9 Bytes could be saved if we haven't to handle -0
> 3 votes

# Answer
# QuadS, 31 bytes

Equivalent of my APL answer.

```
≢¨⍵
^-?(0|[1-9]\d*)(\.\d+)?$
⍵N

```

Try it online!
> 1 votes

# Answer
# Retina 0.8.2, 35 bytes

```
^-?(0|[1-9]\d*)(?<1>\.\d+)?$|.+
$#1

```

Try it online! Link includes test cases. Outputs `2` for float, `1` for integer and `0` for everything else. Explanation:

```
^-?(0|[1-9]\d*)(?<1>\.\d+)?$|.+

```

Try to match an integer with an optional decimal fraction. Capture both the integer and the fraction (if it's present) in capture group `1`. If the input is neither then simply match it all without capturing anything.

```
$#1

```

Output the number of captures of capture group `1`.
> 1 votes

# Answer
## Go, 135 bytes

```
package n
import."strconv"
func f(s string)byte{if _,e:=Atoi(s)
e==nil{return'i'}
if _,e:=ParseFloat(s,64)
e==nil{return'f'}
return'n'}

```

## Go, 418 bytes

Some people have mentioned that the code above doesn't pass all test cases. I realized that the rules in the question don't actually match rules used by programming languages on what qualifies as an integer or float. For example, the rules say that `1e3` is not a float, but in reality it is:

```
package main

import (
   "fmt"
   "strconv"
)

func main() {
   f, err := strconv.ParseFloat("1e3", 64)
   fmt.Println(f, err) // 1000 <nil>
}

```

So I made an edit to handle these rules:

```
package n
import."strconv"
func f(s string)byte{if s[0]=='0'&&s[1]!='.'{return'n'}
if len(s)>=3&&s[:2]=="-0"&&s[2]!='.'{return'n'}
if s[0]=='-'{}else if s[0]>='0'&&s[0]<='9'{}else{return'n'}
if s[len(s)-1]>='0'&&s[len(s)-1]<='9'{}else{return'n'}
for _,r:=range s{if r=='-'{}else if r=='.'{}else if r>='0'&&r<='9'{}else{return'n'}}
if _,e:=Atoi(s);e==nil{return'i'}
if _,e:=ParseFloat(s,64);e==nil{return'f'}
return'n'}

```

Test:

```
package n

import (
   "fmt"
   "testing"
)

type testType struct {
   in string
   out byte
}

var tests = []testType{
   {"+1.0", 'n'}, {"--1.0", 'n'}, {"-0", 'i'}, {"-0.0", 'f'}, {"-001.1", 'n'},
   {"-1e3", 'n'}, {"-2", 'i'}, {".1", 'n'}, {"00", 'n'}, {"042", 'n'},
   {"1.", 'n'}, {"1.0", 'f'}, {"1.0.0", 'n'}, {"1.00", 'f'}, {"1.0ec3", 'n'},
   {"123", 'i'}, {"1e+3", 'n'}, {"1e-3", 'n'}, {"1e3", 'n'}, {"42", 'i'},
   {"62727.0033", 'f'}, {"644c.33", 'n'}, {"NaN", 'n'},
}

func TestNumber(t *testing.T) {
   for _, test := range tests {
      out := f(test.in)
      if out != test.out {
         fmt.Printf("%v %c %c\n", test.in, test.out, out)
      }
   }
}

```
> 1 votes

# Answer
# PowerShell, 56 bytes

Takes a single number as a string; outputs 0 for other, 3 for integer, and 4 for float

```
("$args"-match"^-?(0|[1-9]\d*)(\.\d+)?$")+$matches.Count

```

Try it online!

# PowerShell (Alternate Regex), 56 bytes

```
("$args"-match"^-?((?!0)\d+|0)(\.\d+)?$")+$matches.Count

```

Try it online!
> 1 votes

# Answer
# Charcoal, 55 bytes

```
≔⁰ηＦＳ≡ι-≔∨¬η¹⁵η.≔⎇⊖↔⁻⁸η¹⁵¦⁵η0≔⎇›²η⁷｜⁸ηη≔｜⁹⎇Σιη⁶η§00121η

```

Try it online! Link is to verbose version of code. Outputs `2` for float, `1` for integer and `0` for everything else. Explanation: Implements a state machine (see below).

```
≔⁰η

```

Start in state 0.

```
ＦＳ≡ι

```

Switch over the input string's characters.

```
-≔∨¬η¹⁵η

```

`-` transitions from state `0` to state `1` and from any other state to state `15`.

```
.≔⎇⊖↔⁻⁸η¹⁵¦⁵η

```

`.` transitions from states `7` or `9` to state `5` and from any other state to state `15`.

```
0≔⎇›²η⁷｜⁸ηη

```

`0` transitions from states `1` or `2` to state `7` and from any other state to the result of a bitwise OR with `8`.

```
≔｜⁹⎇Σιη⁶η

```

Any other digit transitions by the result of a bitwise OR with `9` and any other character transitions to state `15` (obtained via a bitwise OR of `6` with `9`).

```
§00121η

```

Look up the acceptance value of the final state, modulo 5. State `13` is reached for floats. State `7` is reached for `0` and state `9` is reached for other integers. States `0`, `1`, `5` and `15` cover everything else. Transition table:

|  | - | . | 0 | \d | X | Pattern |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | 1 | 15 | 7 | 9 | 15 | ^ |
| 1 | 15 | 15 | 7 | 9 | 15 | ^- |
| 5 | 15 | 15 | 13 | 13 | 15 | ^-?(0|\[1-9\]\d+)\\. |
| 7 | 15 | 5 | 15 | 15 | 15 | ^-?0 |
| 9 | 15 | 5 | 9 | 9 | 15 | ^-?\[1-9\]\d+ |
| 13 | 15 | 15 | 13 | 13 | 15 | ^-?(0|\[1-9\]\d+)\\.\d+ |
| 15 | 15 | 15 | 15 | 15 | 15 |  |
> 0 votes

# Answer
# Mathematica, 93 bytes

```
 Which[#~(a=StringMatchQ)~(b=RegularExpression)[c="-?([1-9]\\d*|0)"],0,#~a~b[c<>"\\.\\d+"],1]&

```

`Which`, being Mathematica's if-elseif chain. Just tests if the argument matches a regular expression for ints, then floats, all wrapped up in a lambda / pure function.

0 = int
1 = float
Null = neither

# Mathematica, 81 bytes

Using the "a different value" Mathematica is fine returning complex symbols:

```
 #~(a=StringMatchQ)~(b=RegularExpression)[c="-?([1-9]\\d*|0)"]-#~a~b[c<>"\\.\\d+"]&

```

Parenthesis and square brackets remain for order of operations.

-False + True = int
False - True = float
0 = neither
> -1 votes

---
Tags: code-golf, string, number, parsing, classification
---