title: Find the n-th perfect power!

text:
# Question
Title: Find the n-th perfect power!
A perfect power is a number of the form \\$a^b\\$, where \\$a\>0\\$ and \\$b\>1\\$.

For example, \\$125\\$ is a perfect power because it can be expressed as \\$5^3\\$.

# Goal

Your task is to write a program/function that finds the \\$n\\$-th perfect power, given a positive integer \\$n\\$.

# Specs

* The first perfect power is \\$1\\$ (which is \\$1^2\\$).
* Input/output in any reasonable format.
* Built-ins are **allowed**.

# Further information

# Scoring

This is . Shortest solution in bytes wins.

# Testcases

```
input  output
1      1
2      4
3      8
4      9
5      16
6      25
7      27
8      32
9      36
10     49

```

# Answer
> 8 votes
# Mathematica, 34 bytes

```
(Union@@Array[#^#2#&,{#,#}])[[#]]&

```

Generates an \\$n\times n\\$ array \\$A\_{ij} = i^{1+j}\\$, flattens it, and returns the \\$n\\$th element.

# Answer
> 8 votes
# Jelly, 11 bytes

```
µÆE;¬g/’µ#Ṫ

```

Try it online!.

### Background

Every positive integer \\$k\\$ can be factorized uniquely as the product of powers of the first \\$m\\$ primes, i.e., \\$k=p\_1^{\alpha\_1}\cdots p\_m^{\alpha\_m}\\$, where \\$\alpha\_m\>0\\$.

We have that \\$a^b\\$ (\\$b\>1\\$) for some positive integer \\$a\\$ if and only if \\$b\\$ is a divisor of all exponents \\$\alpha\_j\\$.

Thus, an integer \\$k \> 1\\$ is a perfect power if and only if \\$\gcd(α\_1, ⋯, α\_m) ≠ 1\\$.

### How it works

```
µÆE;¬g/’µ#Ṫ  Main link. No arguments.

µ            Make the chain monadic, setting the left argument to 0.
        µ#   Find the first n integers k, greater or equal to 0, for which the
             preceding chain returns a truthy value.
             In the absence of CLAs, n is read implicitly from STDIN.
 ÆE          Compute the exponents of the prime factorization of k.
   ;¬        Append the logical NOT of k, i.e., 0 if k > 0 and 1 otherwise.
             This maps 1 -> [0] and [0] -> [1].
     g/      Reduce the list of exponents by GCD.
             In particular, we achieved that 1 -> 0 and 0 -> 1.
       ’     Decrement; subtract 1 from the GCD.
             This maps 1 to 0 (falsy) and all other integers to a truthy value.
          Ṫ  Tail; extract the last k.

```

# Answer
> 4 votes
# 05AB1E, 12 bytes

Code:

```
LD>m€`{Ú`¹<@

```

Uses **CP-1252** encoding. Try it online!.

# Answer
> 3 votes
# Octave, ~~57~~ ~~31~~ 30 bytes

```
@(n)unique((1:n)'.^(2:n+1))(n)

```

I just noticed again that Octave does not need `ndgrid` (while Matlab does)=)

# Answer
> 3 votes
## CJam, 16 bytes

```
ri_),_2f+ff#:|$=

```

Test it here.

### Explanation

This uses a similar idea to LegionMammal's Mathematica answer.

```
ri    e# Read input and convert to integer N.
_),   e# Duplicate, increment and turn into range [0 1 ... N].
_2f+  e# Duplicate and add two to each element to get [2 3 ... N+2].
ff#   e# Compute the outer product between both lists over exponentiation.
      e# This gives a bunch of perfect powers a^b for a ≥ 0, b > 1.
:|    e# Fold set union over the list, getting all unique powers generated this way.
$     e# Sort them.
=     e# Retrieve the N+1'th power (because input is 1-based, but CJam's array access
      e# is 0-based, which is why we included 0 in the list of perfect powers.

```

# Answer
> 3 votes
# Jelly, 9 bytes

```
*þḊFQṢị@o

```

Try it online!

As far as I can tell, only the `þ` quick didn't exist when the challenge was posted, but this 10 byter would've worked back then as well as now.

## How it works

```
*þḊFQṢị@o - Main link. Takes n on the left
  Ḋ       - Yield [2, 3, ..., n]
 þ        - Create an n×(n-1) matrix then
            for each entry (i,j) (i = 1,2,...,n and j = 2,3,...n),
            fill it with the following:
*         -   i*j
   F      - Flatten the matrix
    Q     - Remove duplicates
     Ṣ    - Sort
            For all n > 1, this yields an ordered list of perfect powers below n*n
            For n = 1, this yields an empty list
      ị@  - Take the nth item in this list. n = 1 yields 0
        o - Replace 0 with n, to handle n = 1

```

# Answer
> 2 votes
# Sage (version 6.4, probably also others): ~~64~~ 63

```
lambda n:[k for k in range(1+n^2)if(0+k).is_perfect_power()][n]

```

Creates a lambda function that returns `n`th perfect power. We rely on the fact that it is found within the first `n^2` integers. (The `1+n^2` is necessary for `n=1,2`. The `0+k` bit is necessary to convert `int(k)` to `Integer(k)`.)

Byte off for `xrange`-\>`range`, thanks Dennis.

Just a fun fact: `0` is a perfect power by Sage's standards, fortunately, because then `1` is the 1st element of the list, not 0th :)

# Answer
> 2 votes
# Pyth - ~~12~~ 11 bytes

Obvious approach, just goes through and checks all numbers.

```
e.ffsI@ZTr2

```

Test Suite.

# Answer
> 1 votes
# J, 29 bytes

Based on the @LegionMammal978's method.

```
<:{[:/:~@~.[:,/[:(^/>:)~>:@i.

```

## Usage

```
   f =: <:{[:/:~@~.[:,/[:(^/>:)~>:@i.
   f " 0 (1 2 3 4 5 6 7 8 9 10)
1 4 8 9 16 25 27 32 36 49

```

## Explanation

```
<:{[:/:~@~.[:,/[:(^/>:)~>:@i.
                           i.  Create range from 0 to n-1
                        >:     Increments each in that range, now is 1 to n
               [:              Cap, Ignores input n
                    >:         New range, increment from previous range to be 2 to n+1 now
                  ^/           Forms table using exponentation between 1..n and 2..n+1
             ,/                Flattens table to a list
         ~.                    Takes only distinct items
     /:~                       Sorts the list
<:                             Decrements the input n (since list is zero-based index)
  {                            Selects value from resulting list at index n-1

```

# Answer
> 1 votes
# MATL, 9 bytes

```
:tQ!^uSG)

```

Try it online

This is a port of Flawr's Octave solution to MATL, make the matrix of powers up to `n^(n+1)`, and get the `n`-th one.

# Answer
> 1 votes
# Julia, ~~64~~ 32 bytes

```
n->sort(∪([1:n]'.^[2:n+1]))[n]

```

This is an anonymous function that accepts an integer and returns an integer. To call it, assign it to a variable.

The idea here is the same as in LegionMammal's Mathematica answer: We take the outer product of the integers 1 to *n* with 2 to *n* \+ 1, collapse the resulting matrix column-wise, take unique elements, sort, and get the *n*th element.

Try it online! (includes all test cases)

# Answer
> 1 votes
# JavaScript (ES6), 87

```
n=>(b=>{for(l=[i=0,1];b<n*n;++b)for(v=b;v<n*n;)l[v*=b]=v;l.some(x=>n==i++?v=x:0)})(2)|v

```

*Less golfed*

```
f=n=>{
  for(b=2, l=[0,1]; b < n*n; ++b)
    for(v = b; v < n*n;)
      l[v*=b] = v;
  i = 0;
  l.some(x => n == i++ ? v=x : 0);
  return v;
  // shorter alternative, but too much memory used even for small inputs
  // return l.filter(x=>x) [n-1];
}

```

**Test**

```
f=n=>(b=>{for(l=[i=0,1];b<n*n;++b)for(v=b;v<n*n;)l[v*=b]=v;l.some(x=>n==i++?v=x:0)})(2)|v

function test(){
  var v=+I.value
  O.textContent=f(v)
}

test()
```

```
<input type=number id=I value=10><button onclick='test()'>-></button>
<span id=O></span>
```

# Answer
> 1 votes
## Actually, 18 bytes

```
;;u@ⁿr;`;√≈²=`M@░E

```

Try it online! (may not work due to needing an update)

Explanation:

```
;;u@ⁿr;`;√≈²=`M@░E
;;u@ⁿr              push range(n**(n+1))
      ;`;√≈²=`M@░   filter: take if
        ;√≈²=         int(sqrt(x))**2 == x
                 E  get nth element

```

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

```
:1)?v  >n;
$:@@\&31+2>2$:@@:@
:1=?\@$:@*@@1-
:~$~<.1b+1v!?(}:{:~~v?(}:{:v?=}:{
1-:&1=?v~~>~61.     >~1+b1.>&

```

This program requires the input number to be present on the stack before running.

It took quite a lot to reduce the number of wasted bytes down to 7!

After a check to see if the input is `1`, the program checks each number, `n`, from 4 in turn to see if it's a perfect power. It does this by starting with `a=b=2`. If `a^b == n`, we've found a perfect power, so decrement the number of perfect powers left to find - if we've already found the right number, output.

If `a^b < n`, `b` is incremented. If `a^b > n`, `a` is incremented. Then, if `a == n`, we've found that `n` isn't a perfect power, so increment `n`, resetting `a` and `b`.

# Answer
> 1 votes
# Husk, 10 bytes

```
!¹OuṠ×^tḣ→

```

Try it online!

## Explanation

```
!¹OuṠ×^tḣ→ Range 1..n+1 (ḣ called with 1 given an empty list)
    Ṡ      hookf: Ṡ f g x = f (g x) x
     ×^     f: apply power to all possible pairs from two lists
       t    g: tail (1..n → 2..n)
   u       all unique powers
  O        sort in ascending order
!¹         element at index n

```

# Husk, 10 bytes

```
!¹uO§×^…2ḣ

```

Try it online!

Dominic Van Essen's solution.

## Explanation

```
!¹uO§×^…2ḣ
    §      fork: § f g h x = f (g x) (h x)
     ×^     f: apply power to all possible pairs from two lists
       …2   g: inclusive range from 2..n (works for n<2)
         ḣ  h: range from 1..n
   O        sort in ascending order
  u         all unique powers
!¹         element at index n

```

# Answer
> 1 votes
# , 44 bytes

```
n=scan();unique(sort(outer(1:n,2:n,`^`)))[n]

```

Try it online!

Same approach as the Mathematica answer.

# Answer
> 0 votes
## JavaScript (ES7), 104 bytes

```
n=>(a=[...Array(n)]).map(_=>a.every(_=>(p=i**++j)>n*n?0:r[p]=p,i+=j=1),r=[i=1])&&r.sort((a,b)=>a-b)[n-1]

```

Works by computing all powers not greater than n², sorting the resulting list and taking the nth element.

# Answer
> 0 votes
# Java, 126

```
r->{int n,i,k;if(r==1)return r;for(n=i=2,r--;;){for(k=i*i;k<=n;k*=i)if(k==n){i=--r>0?++n:n;if(r<1)return n;}if(--i<2)i=++n;}}

```

# Answer
> 0 votes
# Python 3, 82 bytes

```
f=lambda n,i=0:n and f(n-any(a**b==i for a in range(i)for b in range(i)),i+1)or~-i

```

Try it online!

# Answer
> 0 votes
# 05AB1E, 9 bytes

```
µNDÓ2šθ2@

```

Try it online or verify a few more test cases.

**Explanation:**

```
µ         # Loop until the counter_variable (0 by default) equals the (implicit) input:
 ND       #  Push the current 0-based loop-index `N` twice
   Ó      #  Pop one, and push all its exponents of prime factorization [a,b,c,d,...] in
          #  [2^a,3^b,5^c,7^d,...]
          #  (for N=0 and N=1, this will results in an empty list)
    2š    #  Prepend a 2 (for the edge cases N=0 and N=1)
      θ   #  Pop the list, and leave just the last value
       2@ #  Check if this is larger than or equal to 2
          #  (if it is: implicitly increase the counter_variable by 1)
          # (after the loop, implicitly output the last `N` that's still on the stack)

```

Minor note: the `@` in my answer using the latest 05AB1E version is a builtin for `>=`, whereas the `@` used in *@Adnan*'s existing 05AB1E answer using the legacy 05AB1E version is a builtin to push the \\$n^{th}\\$ item on the stack.

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


# Question
Title: Spot all (anti)diagonals with duplicated values
## Challenge:

Given a matrix input, determine the amount of diagonals and anti-diagonals with duplicated numbers.
So if we have a matrix like this:

```
[[aa,ab,ac,ad,ae,af],
 [ba,bb,bc,bd,be,bf],
 [ca,cb,cc,cd,ce,cf],
 [da,db,dc,dd,de,df]]

```

All diagonals and anti-diagonals would be:

```
[[aa],[ab,ba],[ac,bb,ca],[ad,bc,cb,da],[ae,bd,cc,db],[af,be,cd,dc],[bf,ce,dd],[cf,de],[df],
 [af],[ae,bf],[ad,be,cf],[ac,bd,ce,df],[ab,bc,cd,de],[aa,bb,cc,dd],[ba,cb,dc],[ca,db],[da]]

```

**Example:**

```
[[1,2,1,2,1,2],
 [1,2,3,4,5,6],
 [6,5,4,3,2,1],
 [2,1,2,1,2,1]]

```

All diagonals and anti-diagonals would be:

```
[[1],[2,1],[1,2,6],[2,3,5,2],[1,4,4,1],[2,5,3,2],[6,2,1],[1,2],[1],
 [2],[1,6],[2,5,1],[1,4,2,1],[2,3,3,2],[1,2,4,1],[1,5,2],[6,1],[2]]

```

Removing all diagonals and anti-diagonals only containing unique numbers:

```
[[2,3,5,2],[1,4,4,1],[2,5,3,2],[1,4,2,1],[2,3,3,2],[1,2,4,1]]

```

So the output is the amount of diagonals and anti-diagonals containing duplicated numbers:

```
6

```

## Challenge rules:

* If the input matrix is empty, contains only 1 number, or contains only unique numbers across the entire matrix, the output is always `0`.
* Input is guaranteed to only contain positive digits `[1,9]` (unless it's completely empty).
* The matrix will always be rectangular (i.e. all the rows are the same length).
* I/O is flexible. Input can be taken as a list of lists of integers, or 2D array of integers, or a Matrix-object, as a string, etc. etc. You are also allowed to take one or both of the dimensions of the matrix as additional input if it would save bytes in your language of choice.

## General rules:

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (i.e. TIO).
* Also, adding an explanation for your answer is highly recommended.

## Test cases:

```
Input:                     Output:

[[1,2,1,2,1,2],            6
 [1,2,3,4,5,6],
 [6,5,4,3,2,1],
 [2,1,2,1,2,1]]

[[]]                       0

[[1,2],                    0
 [3,4]]

[[1,1],                    2
 [1,1]]

[[9,9,9],                  6
 [9,9,9],
 [9,9,9]]

[[7,7,7,7],                8
 [7,7,7,7],
 [7,7,7,7]]

[[1,1,1],                  1
 [2,3,4],
 [2,5,1]]

[[1,8,4,2,9,4,4,4],        12
 [5,1,2,7,7,4,2,3],
 [1,4,5,2,4,2,3,8],
 [8,5,4,2,3,4,1,5]]

[[1,2,3,4],                4
 [5,6,6,7],
 [8,6,6,9],
 [8,7,6,5]]

```

# Answer
# Husk, 9 bytes

```
#S≠uṁ∂Se↔

```

Try it online!

## Explanation

```
#S≠uṁ∂Se↔
      S   hook: S f g x = f x (g x)
       e  pair the matrix
        ↔ with its reverse
    ṁ∂    get the antidiagonals of each, in a single list
#         count all diagonals which satisfy the following:
 S        hook: S f g x = f x (g x)
  ≠       diagonal does not equal
   u      itself uniquified?

```
> 2 votes

# Answer
# , ~~92~~ ~~86~~ ~~82~~ 78 bytes

```
function(m,x=row(m),y=col(m),`|`=split,`^`=Map)sum(max^table^c(m|x-y,m|x+y)>1)

```

Try it online!

### Explanation

First, we declare additional variables \\$x\\$ and \\$y\\$ that stand for row and column indices, respectively. Then we can delineate the diagonals and anti-diagonals by taking their difference and sum. E.g., for a 4x4 matrix:

\\$x-y\\$ gives:

`0 -1 -2 -3
 1 0 -1 -2
 2 1 0 -1
 3 2 1 0`

\\$x+y\\$ gives:

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

Now `split(m, x-y)` and `split(m, x+y)` produce the actual lists of diagonals and anti-diagonals, which we join together.

Finally, we count the entries of the resulting list where duplicates are present.

Thanks for bytes saved:

-4 by CriminallyVulgar
-4 by digEmAll
> 10 votes

# Answer
# , ~~21~~ 20 bytes

-1 byte thanks to Jonah!

```
1#.|.,&((~:&#~.)/.)]

```

Try it online!

## Explanation:

```
1#.                   find the sum of the
     ,                concatenation of
       (          )   the result of the verb in the parentheses applied to
                   ]  the input
      &               and
   |.                 the reversed input
        (      )/.    for each diagonal
         ~:&#~.       check if all elements are unique and negate the result

```
> 5 votes

# Answer
# Japt, 31 bytes

```
ËcUî
ËéEÃÕc¡XéYnÃÕ mf fÊk_eZâÃl

```

Try all test cases

Explanation:

```
Ëc                            #Pad each row...
  Uî                          #With a number of 0s equal to the number of rows

ËéEÃÕ                         #Get the anti-diagonals:
ËéEÃ                          # Rotate each row right a number of times equal to the row's index
    Õ                         # Get the resulting columns
     c                        #Add to that...
      ¡XéYnÃÕ                 #The diagonals:
      ¡XéYnÃ                  # Rotate each row left a number of times equal to the row's index
            Õ                 # Get the resulting columns
              mf              #Remove the 0s from each diagonal
                 fÊ           #Remove the all-0 diagonals
                   k_   Ã     #Remove the ones where:
                     eZâ      # The list contains no duplicates
                         l    #Return the number of remaining diagonals

```

I also tried a version based on Kirill L.'s Haskell answer, but couldn't find a good way to "group by a function of the X and Y indices" and the alternative I found wasn't good enough.
> 5 votes

# Answer
# Jelly, 10 bytes

```
ŒD;ŒdQƑÐḟL

```

Try it online! or **Check out the test suite!**

Alternatives:

```
ŒD;ŒdQƑ€¬S
ŒD;ŒdQƑ€ċ0

```

### How it works?

```
ŒD;ŒdQƑÐḟL – Monadic link / Full program.
  ;        – Join:
ŒD           – The diagonals
             with
   Œd        – The anti-diagonals.
       Ðḟ  – Discard the lists that are not:
     QƑ      – Invariant under deduplication.
         L – Length (count them).

```
> 4 votes

# Answer
# JavaScript (ES6),  ~~107 105 101~~  98 bytes

```
f=(m,d=s=1)=>(m+0)[s-=~d/2]?m.some(o=(r,y)=>!r.every((v,x)=>x+d*y+m.length-s?1:o[v]^=1))+f(m,-d):0

```

Try it online!

### Note

The way this code is golfed, the anti-diagonal consisting of the sole bottom-left cell is never tested. That's OK because it can't possibly contain duplicated values.

### Commented

```
f = (                    // f = recursive function taking:
  m,                     //   m[] = input matrix
  d =                    //   d   = direction (1 for anti-diagonal or -1 for diagonal)
  s = 1                  //   s   = expected diagonal ID, which is defined as either the sum
) =>                     //         or the difference of x and y + the length of a row
  (m + 0)[               //
    s -= ~d / 2          // increment s if d = -1 or leave it unchanged otherwise
  ] ?                    // if s is less than twice the total number of cells:
    m.some(o =           //   o = object used to store encountered values in this diagonal
    (r, y) =>            //   for each row r[] at position y in m[]:
      !r.every((v, x) => //     for each cell of value v at position x in r[]:
        x + d * y +      //       x + d * y + m.length is the ID of the diagonal
        m.length - s ?   //       if it's not equal to the one we're looking for:
          1              //         yield 1
        :                //       else:
          o[v] ^= 1      //         toggle o[v]; if it's equal to 0, v is a duplicate and
                         //         every() fails which -- in turn -- makes some() succeed
      )                  //     end of every()
    )                    //   end of some()
    + f(m, -d)           //   add the result of a recursive call in the opposite direction
  :                      // else:
    0                    //   stop recursion

```
> 4 votes

# Answer
# 05AB1E, 25 bytes

```
í‚εεygÅ0«NFÁ]€ø`«ʒ0KDÙÊ}g

```

Try it online! or as a Test Suite

**Explanation**

```
í                          # reverse each row in input
 ‚                         # and pair with the input
  ε                        # for each matrix
   ε                       # for each row in the matrix
    ygÅ0«                  # append len(row) zeroes
         NFÁ               # and rotate it index(row) elements to the right
            ]              # end loops
             €ø            # transpose each matrix
               `«          # append them together
                 ʒ     }   # filter, keep only rows that
                  0K       # when zeroes are removed
                    DÙÊ    # are not equal to themselves without duplicate values
                        g  # push length of the result

```

I feel like I've missed something here.
Need to try and golf this more later.
> 4 votes

# Answer
# Python 2, ~~144~~ 136 bytes

```
lambda m:sum(l(set(d))<l(d)for d in[[r[i*x+o]for i,r in enumerate(m)if-1<i*x+o<l(r)]for o in range(-l(`m`),l(`m`))for x in[-1,1]])
l=len

```

Try it online!
> 3 votes

# Answer
# Octave, 98 bytes

```
@(A)nnz([(q=@(Q)arrayfun(@(n)nnz(z=diag(Q,n))-nnz(unique(z)),-([m,n]=size(Q)):n))(A),q(rot90(A))])

```

Try it online!
> 3 votes

# Answer
## Haskell, ~~118~~ 112 bytes

```
import Data.List
r#(a:b)=sum[1|(/=)=<<nub$[h|h:_<-a:r]]+[t|_:t<-a:r]#b
[]#_=0
a#_=a#[[]]
h x=[]#x+[]#(reverse x)

```

Try it online!

```
r#(a:b)                      -- function '#' calculates the ant-diagonals of a matrix
                             -- where 'a' is the first row and 'b' all the others
                             -- as we recursively walk down the rows of the matrix,
                             -- 'r' holds the rows from before with the respective
                             -- head dropped
                             --
          [h|h:_<-a:r]       -- if the heads of the the current row and the rows
                             -- before
       (/=)=<<nub$           -- contain duplicates
    [1|                ]     -- make a singleton list [1] (else the empty list)
 sum                         -- and take the sum thereof
      +                      -- and add
             #               -- a recursive call with
 [t|_:t<-a:r]                -- the tails of the current row and the rows before
              b              -- and the rows below
                             --
[]#_=0                       -- base case if there aren't any tails anymore, return 0
a#_=a#[[]]                   -- if there are tails, but no further rows below,
                             -- continue with tails

h x=[]#x+[]#(reverse x)      -- main function, call '#' with input matrix 'x'
                             -- and the reverse of it to get the number of diagonals
                             -- and anti-diagonals. Recursion starts with no
                             -- rows before the 1st row.

-- example trace of function '#'
-- input matrix:
--   [[1,2,3,4],
--    [5,6,7,8],
--    [9,9,9,9]]
--
--  | r         a          b              a:r          heads   tails (r of next call)
-- -+----------------------------------------------------------------------------------
-- 1| []        [1,2,3,4]  [[5,6,7,8],    [[1,2,3,4]]  [1]     [[2,3,4]]
--  |                       [9,9,9,9]]
--  |
-- 2| [[2,3,4]]  [5,6,7,8]  [[9,9,9,9]]   [[5,6,7,8],  [5,2]   [[6,7,8],
--  |                                      [2,3,4  ]]           [3,4  ]]
--  |
-- 3| [[6,7,8],  [9,9,9,9]  []            [[9,9,9,9],  [9,6,3] [[9,9,9],
--  |  [3,4  ]]                            [6,7,8  ],           [7,8  ]
--  |                                      [3,4    ],           [4    ]
--  |
--  | ....

```
> 3 votes

# Answer
# Charcoal, ~~61~~ ~~56~~ 53 bytes

```
Ｆ²ＦＬθＦＬ§θ⁰Ｆ⟦⁻κ×⊖⊗ιλ⟧⊞υ⊞Ｏ⎇∧λ﹪⁺μιＬθ⊟υ⟦⟧§§θμλＩＬΦυ⊙ι‹⌕ιλμ

```

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

```
Ｆ²

```

Loop over forward and reverse diagonals; `i=0` represents forward diagonals while `i=1` represents reverse diagonals.

```
ＦＬθ

```

Loop over each row index. This represents the index of the start of the diagonal.

```
ＦＬ§θ⁰«

```

Loop over each column index.

```
Ｆ⟦⁻κ×⊖⊗ιλ⟧

```

Calculate the row index of the diagonal at this column index. I use a `for` loop over a single-element array instead of an assignment as this avoids having to wrap the assignment into a block with the following statement, thus saving a byte.

```
⎇∧λ﹪⁺μιＬθ

```

Check whether this is the first column or the diagonal is about to wrap around between bottom and top.

```
⊟υ

```

If it isn't then pop the last list from the list of lists.

```
⟦⟧

```

if it is then start a new empty list.

```
⊞Ｏ...§§θμλ

```

Add the current diagonal entry to that list.

```
⊞υ

```

And push that list (back) to the list of lists.

```
ＩＬΦυ⊙ι‹⌕ιλμ

```

Count the number of lists that contain duplicates.

Let's take an example when `i=0` and `k=1`. This means that we've already collected two diagonals, `[[1,1,5,2],[9,4,3,5]]`. Here's our input:

```
 1 8 4 2 9 4 4 4
[5]1 2 7 7 4 2 3
 1 4 5 2 4 2 3 8
 8 5 4 2 3 4 1 5

```

We then loop `l` from `0` to `7`. This advances both the row and column by 1 each time:

```
 1 8 4 2 9 4 4 4
[5]1 2 7 7 4 2 3
 1[4]5 2 4 2 3 8
 8 5[4]2 3 4 1 5

```

The list is now `[[1,1,5,2],[9,4,3,5],[5,4,4]]`. However when `l` is `3`, we have `k+l=4`, a multiple of the height of the array. This means that we need to start a new list: `[[1,1,5,2],[9,4,3,5],[5,4,4],[]]`. We then continue to collect diagonal elements:

```
 1 8 4[2]9 4 4 4
[5]1 2 7[7]4 2 3
 1[4]5 2 4[2]3 8
 8 5[4]2 3 4[1]5

```

The list is now `[[1,1,5,2],[9,4,3,5],[5,4,4],[2,7,2,1]]`. Now when `l` is `7`, we have `k+l=8`, another multiple of the height of the array. This means that we need to start a new list, which ends up with the last element of that diagonal: `[[1,1,5,2],[9,4,3,5],[5,4,4],[2,7,2,1],[4]]`.

```
 1 8 4[2]9 4 4[4]
[5]1 2 7[7]4 2 3
 1[4]5 2 4[2]3 8
 8 5[4]2 3 4[1]5

```

By collecting wrapping diagonals starting at the first element of each row we eventually accumulate all of the diagonals of the array.
> 2 votes

# Answer
# Wolfram Language (Mathematica), ~~99 98 96 94~~ 83 bytes

```
Count[DuplicateFreeQ@Diagonal[#,i]~Table~{i,-t,t=#~Total~2}&/@{#,Reverse@#},1<0,2]&

```

Try it online!

* `Function[a,a~Diagonal~#&/@Range[t=-#~Total~2,-t]]` gets all diagonals of `a`-- which works because `#~Total~2` is larger than any dimension of `a`.
> 2 votes

# Answer
# APL+WIN, 69 bytes

Prompts for a 2d matrix of the form 4 6⍴1 2 1 2 1 2 1 2 3 4 5 6 6 5 4 3 2 1 2 1 2 1 2 1

This yields:

```
1 2 1 2 1 2
1 2 3 4 5 6
6 5 4 3 2 1
2 1 2 1 2 1

+/~(v⍳¨v)≡¨⍳¨⍴¨v←(v←⊂[1](⌽0,⍳1↓n)⌽(n⍴0),m,((n←0 ¯1+↑⍴m)⍴0),⌽m←⎕)~¨0

```

Try it online! Courtesy of Dyalog Classic

Explanation:

```
(⌽0,⍳1↓n)⌽(n⍴0),m pad m with zeros to isolate diagonals

((n←0 ¯1+↑⍴m)⍴0),⌽m pad rotated m with zeros to isolate anti-diagonals

```

Yields:

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

v←(v←⊂[1](.....)~¨0 enclose the diagonals as a nested vector with padded zeros removed

+/~(v⍳¨v)≡¨⍳¨⍴¨v identify diagnols with duplicate entries and sum

```
> 1 votes

# Answer
# TSQL, ~~140~~ 128 bytes

Found a way to golf 12 characters. This is no longer the longest solution.

Golfed:

```
SELECT sum(iif(y+x=j+i,1,0)+iif(y-x=j-i,1,0))FROM
@,(SELECT x i,y j,max(y)over()m,v w
FROM @)d WHERE(x*y=0or m=y)and v=w and x<i

```

Ungolfed:

```
DECLARE @ table(v int,x int,y int)
-- v = value
-- x = row
-- y = column
INSERT @ values
(1,0,0),(2,0,1),(1,0,2),(2,0,3),(1,0,4),(2,0,5),
(1,1,0),(2,1,1),(3,1,2),(4,1,3),(5,1,4),(6,1,5),
(6,2,0),(5,2,1),(4,2,2),(3,2,3),(2,2,4),(1,2,5),
(2,3,0),(1,3,1),(2,3,2),(1,3,3),(2,3,4),(1,3,5)

SELECT sum(iif(y+x=j+i,1,0)+iif(y-x=j-i,1,0))
FROM @,(SELECT x i,y j,max(y)over()m,v w FROM @)d
WHERE
  (x*y=0or m=y)
  and v=w
  and x<i

```

**Try it out**
> 1 votes

# Answer
# Perl 5, ~~89~~ 82 bytes

```
map{$i=0;map{$a[$x+$i].=$_;$b[@F-$x+$i++].=$_}/\d/g;$x++}@F;$_=grep/(.).*\1/,@a,@b

```

TIO
> 1 votes

---
Tags: code-golf, number, arithmetic, matrix
---


title: Digital Diversity

text:
# Question
Title: Digital Diversity
A positive integer may be represented in an integer base \\$1 \le b \< \infty\\$.

When converted to that base it has some number of distinct digits.

Any positive integer in base \\$1\\$ has \\$1\\$ distinct digit.

Most positive integers in base \\$2\\$ have \\$2\\$ distinct digits, the exceptions being those of the form \\$2^n - 1\\$, which only have \\$1\\$.

So the first positive integer that may be represented in an integer base with \\$1\\$ unique digit is \\$1\\$ and the first that may be represented with \\$2\\$ distinct digits is \\$2\\$.

We can say that \\$1\\$ is the first integer with digital diversity \\$1\\$ and \\$2\\$ is the first integer with digital diversity \\$2\\$.

### Challenge:

Given a positive integer \\$n\\$ return the first positive integer (in base ten\*) that has a digital diversity of \\$n\\$.

* if your language only supports a specific base (e.g. unary or binary) then you may output in that base.

Your algorithm must *work in theory* for any positive integer input: it *may* fail because the precision of your language's integer is too small for the output; but *may not* fail because base conversion is only defined up to some limit.

### Test cases

```
input  output
   1     1
   2     2
   3     11
   4     75
   5     694
   6     8345
   7     123717
  17     49030176097150555672
  20     5271200265927977839335179
  35     31553934355853606735562426636407089783813301667210139
  63     3625251781415299613726919161860178255907794200133329465833974783321623703779312895623049180230543882191649073441
 257     87678437238928144977867204156371666030574491195943247606217411725999221158137320290311206746021269051905957869964398955543865645836750532964676103309118517901711628268617642190891105089936701834562621017362909185346834491214407969530898724148629372941508591337423558645926764610261822387781382563338079572769909101879401794746607730261119588219922573912353523976018472514396317057486257150092160745928604277707892487794747938484196105308022626085969393774316283689089561353458798878282422725100360693093282006215082783023264045094700028196975508236300153490495688610733745982183150355962887110565055971546946484175232

```

This is , the shortest solution in bytes wins.

**OEIS: A049363** \- also smallest pandigital number in base n.

# Answer
# Jelly, 4 bytes

```
ṖaWḅ

```

Try it online! or verify all test cases

### How it works

```
ṖaWḅ  Main link. Argument: n

Ṗ     Pop; yield [1, 2, 3, ..., n-1].
  W   Wrap; yield [n].
 a    Logical AND; yield [n, 2, 3, ..., n-1].
   ḅ  Convert the result from base n to integer.

```
> 11 votes

# Answer
# Python, 40 bytes

```
f=lambda n,k=1:n*(n<k+2)or-~f(n,k+1)*n-k

```

Test it on Ideone.

### How it works

A number with **n** distinct digits must clearly be expressed in base **b ≥ n**. Since our goal is to minimize the number, **b** should also be as small as possible, so **b = n** is the logical choice.

That leaves us with arranging the digits **0, …, n-1** to create a number as small as possible, which means the most significant digits must be kept as small as possible. Since the first digit cannot be a **0** in the canonical representation, the smallest number is
**(1)(0)(2)...(n-2)(n-1)n = nn-1 \+ 2nn-3 \+ … + (n-2)n + (n-1)**, which **f** computes recursively.
> 9 votes

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

This is a very *very* ***very**!* fast, iterative solution.

```
n=r=input();k=2
while k<n:r=r*n+k;k+=1
print r

```

**Try it online**

There's no recursion, so it works for large input. Here's the result of `n = 17000` (takes 1-2 seconds):

http://pastebin.com/UZjgvUSW
> 6 votes

# Answer
## JavaScript (ES6), 29 bytes

```
f=(b,n=b)=>n>2?f(b,--n)*b+n:b

```
> 5 votes

# Answer
# J, 9 bytes

```
#.],2}.i.

```

Based on @Dennis' method.

## Usage

```
   f =: #.],2}.i.
   (,.f"0) >: i. 7
1      1
2      2
3     11
4     75
5    694
6   8345
7 123717
   f 17x
49030176097150555672

```

## Explanation

```
#.],2}.i.  Input: n
       i.  Get range, [0, 1, ..., n-1]
    2}.    Drop the first 2 values, [2, 3, ...., n-1]
  ]        Get n
   ,       Prepend it, [n, 2, 3, ..., n-1]
#.         Convert that to decimal from a list of base-n digits and return

```

There is an alternative solution based on using the permutation index. Given input *n*, create the list of digits `[0, 1, ..., n]`, and find the permutation using an index of *n*!, and convert that as a list of base-*n* digits. The corresponding solution in J for **12 bytes**

```
#.]{.!A.i.,]  Input: n
        i.    Make range [0, 1, ..., n-1]
           ]  Get n
          ,   Join, makes [0, 1, ..., n-1, n]
     !        Factorial of n
      A.      Permutation index using n! into [0, 1, ..., n]
  ]           Get n
   {.         Take the first n values of that permutation
              (This is to handle the case when n = 1)
#.            Convert that to decimal from a list of base-n digits and return

```
> 5 votes

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

```
->n{s=n;(2...n).map{|d|s=s*n+d};s}

```

The answer for a given `n` takes the form `10234...(n-1)` in base `n`. Using `n=10` as an example:

Start with `n`: `10`

Multiply by `n` and add 2: `102`

Mutliply by `n` and add 3: `1023`

And so on.

EDIT: Shorter to use map, it seems.

EDIT 2: Thanks for the tip, m-chrzan!
> 4 votes

# Answer
## Haskell, 31 bytes

```
f n=foldl((+).(*n))n[2..n-1]

```

Converts the list `[n,2,3,...,n-1]` to base `n` using Horner's method via folding. A less golfed version of this is given on the OEIS page.

Thanks to nimi for 3 bytes!
> 3 votes

# Answer
## CJam, 9 bytes

```
ri__,2>+b

```

Try it online!

### Explanation

```
ri   e# Read input N.
__   e# Make two copies.
,    e# Turn last copy into range [0 1 2 ... N-1].
2>   e# Discard up to two leading values.
+    e# Prepend a copy of N.
b    e# Treat as base-N digits.

```
> 3 votes

# Answer
## CJam (9 bytes)

```
qi_,X2$tb

```

Online demo

### Dissection

Obviously the smallest number with digital diversity `n` is found by base-converting `[1 0 2 3 ... n-1]` in base `n`. However, note that the base conversion built-in doesn't require the digits to be in the range `0 .. n-1`.

```
qi    e# Read integer from stdin
_,    e# Duplicate and built array [0 1 ... n-1]
X2$t  e# Set value at index 1 to n
b     e# Base conversion

```

Note that in the special case `n = 1` we get `1 [0] 1 1 tb` giving `1 [0 1] b` which is `1`.
> 3 votes

# Answer
# 05AB1E, 9 bytes

```
DL¦¨v¹*y+

```

Try it online!

**Explanation**

`n = 4` used for example.

```
D           # duplicate input
            # STACK: 4, 4
 L          # range(1, a)
            # STACK: 4, [1,2,3,4]
  ¦¨        # remove first and last element of list
            # STACK: 4, [2,3]
    v       # for each y in list
     ¹*     # multiply current stack with input
       y+   # and add y
            # STACK, first pass: 4*4+2 = 18
            # STACK, second pass: 18*4+3 = 75

```
> 3 votes

# Answer
# C++ -  181  55

Was about to post that real cool solution using `<numeric>`:

```
#import <vector>
#import <numeric>
using namespace std;int f(int n){vector<int> v(n+1);iota(v.begin(),v.end(),0);swap(v[0],v[1]);return accumulate(v.begin(),v.end()-1,0,[n](int r,int a){return r*n+a;});}

```

and then i realized it is **way** easier:

```
int g(int n){int r=n,j=2;for(;j<n;)r=r*n+j++;return r;}

```
> 2 votes

# Answer
# Perl 6,  ~~34 31~~  30 bytes

Translated from the Haskell example on the OEIS page.

```
{(1,0,|(2..^$^n)).reduce: $n×*+*}        # 34
{(1,0,|(2..^$^n)).reduce: $n* *+*}       # 34

{reduce $^n×*+*,1,0,|(2..^$n)}           # 31
{[[&($^n×*+*)]] 1,0,|(2..^$n)}           # 31

{reduce $_×*+*,1,0,|(2..^$_)}            # 30

```
* `[&(…)]` turns  into an in-place infix operator
* The `[…]` shown above turns an infix op into a fold (left or right depending on the operator associativity)

## Expanded:

```
{
  reduce

    # declare the blocks only parameter ｢$n｣ ( the ｢^｣ twigil )
    # declare a WhateverCode lambda that takes two args ｢*｣
    $^n × * + *

    # a list that always contains at least (1,0)
    1, 0,
    # with a range slipped in
    |(
      2 ..^ $n # range from 2 up-to and excluding ｢$n｣
               # it is empty if $n <= 2
    )
}

```

## Usage:

```
my &code = {reduce $_×*+*,1,0,|(2..^$_)}

say code 1; # 1
say code 2; # 2
say code 3; # 11
say code 4; # 75
say code 7; # 123717

# let's see how long it takes to calculate a largish value:

my $start-time = now;
$_ = code 17000;
my $calc-time = now;
$_ = ~$_; # 25189207981120412047...86380901260421982999
my $display-time = now;

say "It takes only { $calc-time - $start-time } seconds to calculate 17000";
say "but { $display-time - $calc-time } seconds to stringify"

# It takes only 1.06527824 seconds to calculate 17000
# but 5.3929017 seconds to stringify

```
> 2 votes

# Answer
# Brain-Flak, ~~84~~ 76 bytes

*Thanks to Wheat Wizard for golfing 8 bytes*

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

```

Try it online!

## Explanation

The program pushes the values from `0` to `n-1` to the stack replaces the top `0` and `1` with `1` and `0`. Then it multiplies the top of the stack by `n` and adds the value below it until there is only one value remaining on the stack.

Essentially it finds the digits for the smallest number in base `n` that contains `n` different digits (for `n` \> 1 it's always of the form `1023...(n-1)`). It then calculates the number given the digits and the base.

### Annotated Code

```
(({})<>)       # Pushes a copy of n to the right stack and switches to right stack
{(({}[()]))}{} # While the top of the stack != 0 copy the top of the stack-1
               #   and push it
(<{}{}>)       # Discard the top two values (0 and 1 for n > 1) and push 0
((()))         # Push 1 twice (second time so that the loop is works properly)
{{}            # Loop while stack height > 1
  (            #   Push...
    {<({}[()])><>({})<>}{} # The top value of the stack * n
    {}         #     Plus the value below the top of the stack
  )            #   End push
([][()])}{}    # End loop

```
> 2 votes

# Answer
# Japt, 8 bytes

```
o1 hU ìU

```

Try it
> 2 votes

# Answer
# Rockstar, 79 bytes

```
listen to N
cast N
X's1
let T be N
while N-X-1
let X be+1
let T be T*N+X

say T

```

Try it here (Code will need to be pasted in)
> 2 votes

# Answer
# Julia, 26 bytes

```
\(n,k=n)=k<3?n:n\~-k*n+~-k

```

Try it online!
> 1 votes

# Answer
# ShapeScript, 25 bytes

```
_0?1'1+@2?*1?+@'2?2-*!#@#

```

Input is in unary, output is in decimal. Try it online!
> 1 votes

# Answer
# PHP, 78 Bytes

```
for(;$i<$a=$argn;)$s=bcadd($s,bcmul($i<2?1-$i:$i,bcpow($a,$a-1-$i++)));echo$s;

```

Online Version

60 Bytes works only till n=16 with the precision in the testcases

For n=144 INF

n=145 NAN

```
for(;$j<$a=$argn;)$t+=($j<2?1-$j:$j)*$a**($a-1-$j++);echo$t;

```
> 1 votes

# Answer
# k, 12 bytes

Based off of Dennis' answer.

```
{x/x,2+!x-2}

```
> 1 votes

# Answer
# JavaScript (ES6), 39 bytes

Does not use `=>`

```
function f(b,n){throw f(b,n>2?--n:1)*b}

```
> 1 votes

# Answer
# Husk, 7 bytes

```
B¹ṙ_1tḣ

```

Try it online!
> 1 votes

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


title: Output diagonal positions of me squared

text:
# Question
Title: Output diagonal positions of me squared
Given a number `n`, Output an ordered list of 1-based indices falling on either of the diagonals of an `n*n` square matrix.

## Example:

For an input of `3`:

The square shall be:

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

```

Now we select all the indices represented by `\`, `/` or `X` (`#` or non-diagonal positions are rejected)

```
\ # /
# X #
/ # \

```

The output shall be:

```
[1,3,5,7,9]

```

# Test cases:

```
1=>[1]
2=>[1,2,3,4]
3=>[1,3,5,7,9]
4=>[1,4,6,7,10,11,13,16]
5=>[1,5,7,9,13,17,19,21,25]

```

There will be no accepted answer. I want to know the shortest code for each language.

# Answer
# Octave, 28 bytes

```
@(n)find((I=eye(n))+flip(I))

```

Anonymous function that inputs a number and outputs a column vector of numbers.

**Try it online!**
> 10 votes

# Answer
# JavaScript (ES6), 48 bytes

Outputs a dash-separated list of integers as a string.

```
f=(n,k=n*n)=>--k?f(n,k)+(k%~-n&&k%-~n?'':~k):'1'

```

### Formatted and commented

```
f = (n, k = n * n) => // given n and starting with k = n²
  --k ?               // decrement k; if it does not equal zero:
    f(n, k) + (       //   return the result of a recursive call followed by:
      k % ~-n &&      //     if both k % (n - 1) and
      k % -~n ?       //             k % (n + 1) are non-zero:
        ''            //       an empty string
      :               //     else:
        ~k            //       -(k + 1) (instantly coerced to a string)
    )                 //   end of iteration
  :                   // else:
    '1'               //   return '1' and stop recursion

```

### Test cases

```
f=(n,k=n*n)=>--k?f(n,k)+(k%~-n&&k%-~n?'':~k):'1'

;[1,2,3,4,5].forEach(n => console.log(n, '->', f(n)))
```
> 7 votes

# Answer
# , ~~38~~ ~~35~~ ~~34~~ 38 bytes

3 bytes saved when I remembered about the existence of the `which` function... , 1 byte saved thanks to @Rift

```
d=diag(n<-scan());which(d|d[n:1,])

```

+4 bytes for the argument `ec=T` when called as a full program by `source()`

Try it online!

Explanation:

```
n<-scan()            # take input
d=diag(n);           # create an identity matrix (ones on diagonal, zeros elsewhere)
d|d[n:1,]            # coerce d to logical and combine (OR) with a flipped version
which([d|d[n:1,]])   # Find indices for T values in the logical expression above

```
> 7 votes

# Answer
# Jelly, 8 bytes

```
⁼þ`+Ṛ$ẎT

```

Try it online!

Uses Luis Mendo's algorithm on his MATL answer.
> 6 votes

# Answer
# Octave, ~~41~~ 37 bytes

This works in MATLAB too by the way. No sneaky Octave specific functionality :)

```
@(x)unique([x:x-1:x^2-1;1:x+1:x*x+1])

```

Try it online!

### Explanation:

Instead of creating a square matrix, and find the two diagonals, I figured I rather calculate the diagonals directly instead. This was **17** bytes shorter! =)

```
@(x)                                   % Anonymous function that takes 'x' as input
    unique(...                   ...)  % unique gives the unique elements, sorted
           [x:x-1:x^2-1                % The anti-diagonal (is that the correct word?)
                       ;               % New row
                        1:x+1:x*x+1])  % The regular diagonal

```

This is what it looks like, without `unique`:

```
ans =
    6   11   16   21   26   31
    1    8   15   22   29   36

```

Yes, I should probably have flipped the order of the diagonals to make it more human-friendly.
> 5 votes

# Answer
# MATL, 6 bytes

```
XytP+f

```

Try it online!

### Explanation

Same approach as my Octave answer.

Consider input `3` as an example.

```
Xy   % Implicit input. Identity matrix of that size
     % STACK: [1 0 0;
               0 1 0;
               0 0 1]
t    % Duplicate
     % STACK: [1 0 0
               0 1 0
               0 0 1],
              [1 0 0
               0 1 0
               0 0 1]
P    % Flip vertically
     % STACK: [1 0 0
               0 1 0
               0 0 1],
              [0 0 1
               0 1 0
               1 0 0]
+    % Add
     % STACK: [1 0 1
               0 2 0
               1 0 1]
f    % Linear indices of nonzero entries. Implicit display
     % STACK:[1; 3; 5; 7; 9]

```

Linear indexing is column-major, 1-based. For more information see length-12 snippet here.
> 5 votes

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

```
lambda n:[i+1for i in range(n*n)if i%-~n<1or i%~-n<1]

```

Try it online!
> 4 votes

# Answer
# Mathematica, 42 bytes

```
Union@Flatten@Table[{i,#+1-i}+i#-#,{i,#}]&

```

Try it online!

@KellyLowder golfed it down to..

# Mathematica, 37 bytes

```
##&@@@Table[{i-#,1-i}+i#,{i,#}]⋃{}&

```

and @alephalpha threw away the table!

# Mathematica, 34 bytes

```
Union@@Range[{1,#},#^2,{#+1,#-1}]&

```
> 4 votes

# Answer
# Octave, ~~68~~ 54 bytes

*Thanks to @Stewie Griffin for saving 14 bytes!*

```
@(x)unique([diag(m=reshape(1:x^2,x,x)),diag(flip(m))])

```

Try it online!

# MATLAB, 68 bytes

```
x=input('');m=reshape([1:x*x],x,x);unique([diag(m) diag(flipud(m))])

```

**Explanation:**

```
@(x)                               % Anonymous function
m=reshape([1:x*x],x,x);            % Create a vector from 1 to x^2 and
                                   % reshape it into an x*x matrix.
diag(m)                            % Find the values on the diagonal.
diag(flip(m))                      % Flip the matrix upside down and
                                   % find the values on the diagonal.
unique([])                         % Place the values from both diagonals
                                   % into a vector and remove duplicates.

```
> 4 votes

# Answer
# Proton, 41 bytes

```
n=>[i+1for i:0..n*n if!(i%-~n)or!(i%~-n)]

```

Try it online!
> 2 votes

# Answer
# MATL, 14 bytes

```
U:GeGXytPY|*Xz

```

Try it online!
> 2 votes

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

*-7 bytes thanks to Titus!*

```
f(n,i){for(i=0;i<n*n;i++)i%-~n&&i%~-n||printf("%d ",i+1);}

```

Try it online!
> 2 votes

# Answer
# Javascript, ~~73~~ 63 bytes

*old version*

```
n=>[...Array(y=n*n).keys(),y].filter(x=>(--x/n|0)==x%n||(x/n|0)==n-x%n-1)

```

*Saved 10 bytes thanks to @Shaggy*

```
n=>[...Array(n*n)].map((_,y)=>y+1).filter(x=>!(--x%-~n&&x%~-n))

```

First time golfing! here's hoping I didn't mess up too badly.

```
let f=n=>[...Array(n*n)].map((_,y)=>y+1).filter(x=>!(--x%-~n&&x%~-n));
[1,2,3,4,5].forEach(n=>console.log(f(n)))
```
> 2 votes

# Answer
# C# (.NET Core), 97 83 bytes

```
f=>{var s="[";for(int i=0;i<n*n-1;)s+=i%-~n<1|i++%~-n<1?i+",":"";return s+n*n+"]";}

```

Try it online!

The change here is based on the shift between numbers to find. The two shifts starting at 0 are `n-1` and `n+1`, so if `n=5`, the numbers for `n-1` would be `0,4,8,12,16,20` and for `n+1` would be `0,6,12,18,24`. Combining these and giving 1-indexing (instead of 0-indexing) gives `1,5,7,9,13,17,19,21,25`. The offset from `n` is achieved using bitwise negation (bitwise complement operation), where `~-n==n-1` and `-~n==n+1`.

### Old Version

```
f=>{var s="[";for(int i=0;i<n*n-1;i++)s+=(i/n!=i%n&&n-1-i/n!=i%n?"":i+1+",");return s+$"{n*n}]";}

```

Try it online!

This approach uses the column and row indices for determining if the numbers are on the diagonals. `i/n` gives the row index, and `i%n` gives the column index.

### Returning Only The Number Array

If constructing only the number array is deemed to count towards the byte cost, then the following could be done, based on Dennis.Verweij's suggestion (`using System.Linq;` adds an extra 18 bytes):

C# (.NET Core), 66+18=84 bytes

```
x=>Enumerable.Range(1,x*x).Where(v=>~-v%~-x<1|~-v%-~x<1).ToArray()

```

Try it online!
> 2 votes

# Answer
# Pyth, ~~20~~ 18 bytes

(Here is the initial version.)

```
hMf|<%ThQ1<%TtQ1U*

```

**Test Suite.**

# Pyth, 18 bytes

```
hMf>1*%ThQ%T|tQ1U*

```

**Test Suite.**
> 1 votes

# Answer
# Perl 5, 56 + 1 (-n) = 57 bytes

```
!(($_+1+$_/$,)%$,&&$_%($,+1))&&say++$_ for 0..($,=$_)**2

```

Try it online!
> 1 votes

# Answer
# Java (OpenJDK 8), 71 bytes

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

```

Try it online!

Port of scottinet's answer.
> 1 votes

# Answer
# Japt, 16 bytes

Can't seem to do better than this but I'm sure it's possible. Had to sacrifice 2 bytes for the unnecessary requirement that we use 1-indexing.

```
²õ f@´XvUÉ ªXvUÄ

```

Test it
> 1 votes

# Answer
# Octave, 32 bytes

```
@(n)find((m=abs(--n:-2:-n))==m')

```

Try it online!
> 1 votes

# Answer
# PHP, ~~56~~ 54+1 bytes

+1 byte for `-R` flag

```
for(;$z**.5<$n=$argn;$z++)$z%-~$n&&$z%~-$n||print~+$z;

```

prints numbers prepended by dashes. Run as pipe with `-nR` or try it online.

requires PHP 5.6 or later for `**` operator.
Add one byte for older PHP: Replace `;$z**.5<$n=$argn` with `$z=$argn;$z<$n*$n`.
> 0 votes

# Answer
# Ruby, 45 bytes

```
->n{(n*n).times{|i|i%-~n>0&&i%~-n>0||p(i+1)}}

```

Works internally as zero indexed. checks if `i` modulo `n+1` or `n-1` is 0, if so prints `i+1`.
> 0 votes

# Answer
# Husk, 12 bytes

```
ṁo►L∂Se↔C¹ḣ□

```

Try it online!

indices are unordered.
> 0 votes

---
Tags: code-golf, math, matrix
---


title: Generalized matrix trace

text:
# Question
Title: Generalized matrix trace
Inspiration.

Given (by any means):

* A two-argument (or single argument consisting of a two-element list) black box function, `f: ℤ<sup>+</sup> × ℤ<sup>+</sup> → ℤ<sup>+</sup>` (input and output are 1, 2, 3,…)
* A strictly positive integer matrix with at least two rows and two columns

return the matrix's *function trace*.

What is a *function trace*?

A normal matrix trace is the sum of the major diagonal (top-left to bottom-right) of a matrix:

`[[1,2,3],[4,5,6],[7,8,9]]``[1,5,9]``1+5+9``15`

But instead of summing, we want to apply `f` along the diagonal:

`[[1,2,3],[4,5,6],[7,8,9]]``[1,5,9]``f(f(1,5),9)` or `f(1,f(5,9))`

Please state whether you use left-to-right or right-to-left.

The given matrix and all intermediate values will be strictly positive integers within your language's integer domain. The matrix may be non-square.

### Examples

`f(x,y) = xy`, `[[1,2,3],[4,5,6],[7,8,9]]``1×5×9``45`

`f(x,y) = x<sup>y</sup>`, `[[1,2,3],[4,5,6],[7,8,9]]``159``1`

`f(x,y) = x-y`, `[[4,5,6],[1,2,3]]``4-2``2`

`f(x,y) = <sup>(x+y)</sup>⁄2`, `[[2,3,4],[5,6,7],[8,9,10]]``5` or `7`

`f(x,y) = x+2y`, `[[1,2,3],[4,5,6],[7,8,9]]``47` or `29`

`f(x,y) = max(x,y)`, `[[1,2,3],[4,5,6],[7,8,9]]``max(1,5,9)``9`

`f(x,y) = 2x`, `[[1,2,3],[4,5,6],[7,8,9]]``2` or `4`

`f(x,y) = lcm(x,y)`, `[[2,2,2],[2,2,3],[2,3,3],[4,4,4]]``lcm(2,2,3)``6`

Reference implementation.

# Answer
> 9 votes
# , ~~40~~ 30 bytes

```
function(m,F)Reduce(F,diag(m))

```

Try it online!

Verify the test cases.

Traverses down the diagonal, so left-to-right in this case. For arithmetic operators, you can use `"+"` or backticks around the operators (`+,*,-,%/%,^,%%`)

Pretty straightforward: `Reduce` is R's equivalent to a `fold`, and ~~the diagonal of a matrix is those elements `a_ij` where `i==j`, i.e., where the `row` and `col`umn indices are the same.~~ `diag` has the appropriate behavior for non-square matrices.

# Answer
> 8 votes
# Haskell, 39 bytes

Thanks @Laikoni for helping me fix the previously invalid solution!

```
f!m=foldl1 f[h|h:_<-zipWith drop[0..]m]

```

Associates to the left, try it online! (replace `foldl1` by `foldr1` for right-associative)

# Answer
> 5 votes
# Mathematica, 16 bytes

*-1 byte thanks to Martin Ender.*

```
#~Tr~Fold[g]@*0&

```

Try it online!

## Alternate solution, 17 bytes

```
Fold[g]@*Diagonal

```

Try it online!

# Answer
> 4 votes
# Clean, 56 bytes

```
t[[h:_]]f=h
t[[h]:_]f=h
t[[h:_]:r]f=f h(t[t\\[_:t]<-r]f)

```

Try it online! Folds from right-to-left.

`[t\\[_:t]<-r]` is the same as `map tl r`, but does not need `import StdEnv`.

# Answer
> 4 votes
# Octave, ~~61~~ ~~57~~ 53 bytes

```
function m=g(f,m)for i=diag(m)'(2:end)m=f(m(1),i);end

```

Try it online!

Defines a function `g` which takes a function handle `f` and matrix `m`. On the first iteration, `m(1)` returns the top-left matrix element; after that, it just returns `m`.

# Answer
> 3 votes
# Husk, 7 bytes

Thanks @Zgarb for fixing my submission!

```
Ḟ₁§z!Tŀ

```

Associates to the left, Try it online! (for a right-associative version simply replace  by `F`)

### Explanation

Unfortunately there's no easy way to get the diagonal of a matrix, so most the bytes are for that:

```
Ḟ₁§z!Tŀ  -- function ₁ is the function and matrix A implicit, example:
  §      -- fork A
     T   -- | transpose A: [[1,4,7],[2,5,8],[3,6,9]]
      ŀ  -- | enumerate A: [1,2,3]
   z!    -- and zipWith index: [1,5,9]
Ḟ₁       -- right fold function

```

# Answer
> 3 votes
# Haskell, ~~47~~ ~~45~~ 42 bytes

```
f%((h:t):r)|[]<-t*>r=h|x<-tail<$>r=f h$f%x

```

Try it online! Defines a function `(%)` which takes a function and a matrix as a list of lists as input.

The function is folds from right-to-left:

```
f % [[1,2,3], -> f 1 ( f % [[5,6],   -> f 1 ( f 5 ( f % [[9]] ) ) -> f 1 ( f 5 ( f 9 ) ) )
     [4,5,6],               [8,9]] )
     [7,8,9]]

f % ((h:t):r)              -- (h:t) is the first row and r the remaining rows
 | [] <- t *> r = h         -- a shorter way of checking wether t==[] or r==[]
 | x<-tail<$>r = f h $ f%x -- apply f to h and the result of recursively calling (%) on
                           -- the remaining matrix with the first column removed

```

*Edit: -2 bytes thanks to BMO and -3 bytes thanks to Zgarb!*

# Answer
> 3 votes
# APL (Dyalog Unicode), 7 bytes (Adám's SBCS)

```
⎕/1 1⍉⎕

```

Try it online!

-3 thanks to a suggestion to convert this to a full program by Adám.

Right-to-left.

# Answer
> 2 votes
# Haskell, 44 bytes

```
f#m=foldl1 f$zipWith(!!)m[0..length(m!!0)-1]

```

Try it online!

# Answer
> 2 votes
# 05AB1E, ~~15~~ 10 bytes

Folds from right-to-left
Saved 5 bytes using a new built-in as suggested by *Kevin Cruijssen*

```
Å\`[.g#I.V

```

**Explanation**

Works the same as the old version, except that `Å\` is a new built-in for pushing the main diagonal.

Try it online! or as a Test Suite

**Old Version**

```
¬g£vyNè}[.g#I.V

```

Try it online! or as a Test suite

**Explanation**

```
¬                 # get the head of the input (first row)
 g                # get its length (number of columns)
  £               # take that many rows from input
   v              # for each row_index, row (N,y) do:
    y             # push the row
     Nè           # get the nth element of the row
       }          # end loop
        [.g#      # loop until one value remain on the stack
            I.V   # run the input function

```

# Answer
> 2 votes
# Python 2, 61 bytes

```
lambda f,m:reduce(f,[l[i]for i,l in enumerate(m)if len(l)>i])

```

Try it online!

This works left-to-right.

# Answer
> 2 votes
## JavaScript (ES6), ~~58~~ 56 bytes

```
g=(f,a,r=a[i=0][0],e=a[++i]&&a[i][i])=>e?g(f,a,f(r,e)):r

```

Folds left-to-right. Edit: Saved 2 bytes by using the fact that the array is strictly positive. Alternate solution, also 56 bytes:

```
(f,a,g=r=>(e=a[++i]&&a[i][i])?g(f(r,e)):r)=>g(a[i=0][0])

```

# Answer
> 2 votes
# Java 8, ~~88~~ ~~81~~ ~~70~~ 69 bytes

```
m->{try{for(int i=1;;m[0][0]=f(m[0][0],m[i][i++]));}finally{return;}}

```

Puts the result in the very first cell of the matrix instead of returning an integer (to save a byte).

Try it online.

Both folds `[[1,2,3],[4,5,6],[7,8,9]]` to `f(f(1,5),9)`.

-7 bytes indirectly thanks to *@KamilDrakari* by using a similar trick as he did in his C# answer: instead of having a maximum boundary for the loop based on the rows/columns, simply try-catch the `ArrayIndexOutOfBoundsException`.
-11 bytes replacing `catch(Exception e)` with `finally`.
-1 byte thanks to *@KamilDrakari* again by putting the result in the very first cell.

**Explanation:**

```
m->{                   // Method with integer-matrix parameter and no return-type
  try{for(int i=1;     //  Start the index at 1 (0-based indexing)
          ;)           //   Loop indefinitely:
    m[0][0]=           //    Replace the value in the first cell with:
     f(m[0][0],        //     Call f with the current value of the first cell
       m[i][i++]));}   //     and the next diagonal cell as arguments
  finally{             //  If an ArrayIndexOutOfBoundsException occurred we're done,
    return;}}          //   in which case we'll terminate the method

```

**Black box input format:**

Assumes a named function `int f(int x,int y)` is present, which is allowed according to this meta answer.

I have an abstract class `Test` containing the default function `f(x,y)`, as well as the lambda above:

```
abstract class Test{
  int f(int x,int y){
    return x+y;
  }

  public java.util.function.Consumer<int[][]> c =
    m->{try{for(int i=1;;m[0][0]=f(m[0][0],m[i][i++]));}finally{return;}}
  ;
}

```

For the test cases, I overwrite this function `f`. For example, the first test case is called like this:

```
int[][] inputMatrix = new int[][]{
  new int[]{1,2,3},
  new int[]{4,5,6},
  new int[]{7,8,9}
};
new Test(){
  @Override
  int f(int x,int y){
    return x*y;
  }
}.c.accept(inputMatrix);
System.out.println(inputMatrix[0][0]);

```

# Answer
> 2 votes
# Standard ML (MLton), 59 bytes

```
fun t[h::_]f=h|t([h]::_)f=h|t((h::_)::r)f=f(h,t(map tl r)f)

```

Try it online! Folds from right-to-left.

### Ungolfed:

```
fun trace [h::_]      f = h
  | trace ([h]::_)    f = h
  | trace ((h::_)::r) f = f (h, trace (map tl r) f)

```

Try it online!

# Answer
> 2 votes
# JavaScript, 46 bytes

```
f=>a=>a.reduce((p,l,i)=>l[i]?f(p[0]|p,l[i]):p)

```

Thanks to @Shaggy, use bitwise or save one byte. That's magic.

```
g = f=>a=>a.reduce((p,l,i)=>l[i]?f(p[0]|p,l[i]):p)

c=()=>o.value=g(eval(`(x,y)=>${f.value}`))(m.value.split(/\n/g).map(x=>x.trim().split(/\s+/).filter(v=>v.length).map(v=>+v)).filter(x=>x.length))
```

```
<p>a = <textarea id=m>1 2 3
4 5 6
7 8 9</textarea></p>
<p>f = (x, y) => <input id=f type=text value="x + y" /></p>
<p><button onclick=c()>Calc</button></p>
<p>Result = <output id=o></output></p>
```

# Answer
> 2 votes
# Attache, 14 bytes

```
Fold#/Diagonal

```

Try it online! Set to `f` and call as `f[function, array]`.

## Explanation

This is a fork of two functions: `Fold` and `/Diagonal`. This, for arguments `f` and `a`, is equivalent to:

```
Fold[f, (/Diagonal)[f, a]]

```

`/`, when applied monadically to a function, returns a function that is applied to its last argument. So, this is equivalent to:

```
Fold[f, Diagonal[a]]

```

This folds the function `f` over the main diagonal of `a`.

# Answer
> 2 votes
# AWK, 77 bytes

```
func z(F,M,r){for(e=1;e<M[1]&&e<M[2];)r=@F(r==""?M[1,1]:r,M[++e,e])
return r}

```

Try it online!

I was curious if `AWK` could do functional programming at all. I think this counts.

The "Matrix" is defined as a standard associative array, with extra fields `M[1]=#rows` and `M[2]=#columns`. The function name is passed in as a string which is evaluated via the `@F(...)` syntax. Evaluation is performed left to right. The `r` parameter is a placeholder to prevent overwriting an existing `r` variable and to avoid the need to reinitialize for each call. Typically extra space is added to designate such placeholders in `AWK`, but this is code golf, so every byte counts. :)

The TIO link implements all the test cases.

# Answer
> 1 votes
# SNOBOL4 (CSNOBOL4), 86 bytes

```
T	I =1
	T =M<1,1>
I	I =I + 1
	T =EVAL(F '(T,M<I,I>)')	:S(I)F(RETURN)
	DEFINE('T(M,F)')

```

Try it online!

Defines a function `T` (for `TRACE`) that takes an `ARRAY` and a string `F` that's the name of a function. Folds left-to-right.

Using indirect reference (`$`) doesn't work with functions. So using `EVAL` and passing a string to the name seems to be the only way to get a black-box function in SNOBOL.

Also, it's quite painful to define arrays; however, because invalid array references cause `FAILURE`, this works for non-square arrays -- if `I` is out-of-bounds in either dimension, the `F(RETURN)` forces the function to return.

### Edit:

Possibly, based on this meta post, I may assume that the black-box function `F` is defined under the name `F`, which would drop this to 75 bytes (remove use of `EVAL` and `,F` in the function definition). However, I prefer this version since it's closer to passing a reference to a function.

# Answer
> 1 votes
# Pari/GP, 42 bytes

```
f->a->fold(f,[a[i,i]|i<-[1..min(#a,#a~)]])

```

Try it online!

# Answer
> 1 votes
# JavaScript, ~~61~~ ~~57~~ ~~56~~ ~~52~~ ~~50~~ ~~44~~ 42 bytes

Reduces left to right. Assumes the function is assigned to variable `f`, as per this meta post brought to my attention by Mr. Xcoder & totallyhuman. Can't say as I agree with it as it directly contradicts our existing consensus that we may not assume input is assigned to a pre-defined variable, but I'll take the few bytes saving for now.

```
a=>a.map((y,z)=>x=(n=y[z])?z?f(x,n):n:x)|x

```

---

## Test Cases

```
g=
a=>a.map((y,z)=>x=(n=y[z])?z?f(x,n):n:x)|x
o.innerHTML=[[`f(x,y) = xy`,[[1,2,3],[4,5,6],[7,8,9]],(x,y)=>x*y,45],[`f(x,y) = x<sup>y</sup>`,[[1,2,3],[4,5,6],[7,8,9]],(x,y)=>x**y,1],[`f(x,y) = x-y`,[[4,5,6],[1,2,3]],(x,y)=>x-y,2],[`f(x,y) = <sup>(x+y)</sup>⁄<sub>2</sub>`,[[2,3,4],[5,6,7],[8,9,10]],(x,y)=>(x+y)/2,7],[`f(x,y) = x+2y`,[[1,2,3],[4,5,6],[7,8,9]],(x,y)=>x+2*y,29],[`f(x,y) = max(x,y)`,[[1,2,3],[4,5,6],[7,8,9]],(x,y)=>Math.max(x,y),9],[`f(x,y) = 2x`,[[1,2,3],[4,5,6],[7,8,9]],(x,y)=>2*x,4],[`f(x,y) = lcm(x,y)`,[[2,2,2],[2,2,3],[2,3,3],[4,4,4]],(x,y)=>-~[...Array(x*y).keys()].find(z=>!(++z%x|z%y)),6]].map(([a,b,c,d],e)=>`Test #${++e}:  ${a}\nMatrix:   ${JSON.stringify(b)}\nFunction: ${f=c}\nResult:   ${g(b)}\nExpected: ${d}`).join`\n\n`
```

```
<pre id=o></pre>
```

# Answer
> 1 votes
# C, 76 bytes

```
i,t;f(g,A,n,m)int*A,(*g)();{for(t=*A,i=m+1;--n*--m;t=g(t,*A))A+=i;return t;}

```

Left-to-right.

Try it online!

# Answer
> 1 votes
# Ruby, ~~55~~ 53 bytes

```
->f,m,n=m[i=0][0]{(k=m[i+=1]&.[]i)?(n=f[n,k];redo):n}

```

Try it online!

# Answer
> 1 votes
# C# (Visual C# Compiler), ~~72~~ ~~69~~ 60 bytes

```
m=>{try{for(int i=1;;m[0][0]=f(m[0][0],m[i][i++]));}catch{}}

```

Try it online!

`try/catch` allows the diagonal to be correctly reached by simply going along it and terminating when out of bounds.

3 bytes saved because, as pointed out by Kevin Cruijssen, black-box functions can be assumed to exist under a specific name.

9 bytes saved by returning via modifying an argument.

Thus, the function is called by storing the desired function under the name `f`, calling `trace(matrix)`, and the result is stored in `matrix[0][0]`.

Alternatively, if you really like verbosity,

# C# (Visual C# Compiler), ~~97 + 13 = 110~~ ~~78~~ 69 bytes

```
(int[][]m)=>{try{for(int i=1;;m[0][0]=f(m[0][0],m[i][i++]));}catch{}}

```

Try it online!

32 bytes saved by using a predefined function, because not taking the function as a parameter allowed removing the `System` import and the long `Func` generic type.

# Answer
> 1 votes
# tinylisp, 79 bytes

```
(load library
(d D(q((M)(i(h M)(c(h(h M))(D(map t(t M))))(
(q((F M)(foldl F(D M

```

The last line is an unnamed lambda function that takes a function and matrix and returns the matrix trace. The trace is left-associative (i.e. `f(f(1,5),9)`). Try it online!

### Ungolfed

We define a helper function to compute the diagonal; then `generalized-trace` is merely a small wrapper around the library function `foldl`.

```
(load library)

(def diagonal
 (lambda (matrix)
  (if (head matrix)
   (cons
    (head (head matrix))
    (diagonal (map tail (tail matrix))))
   nil)))

(def generalized-trace
 (lambda (func matrix)
  (foldl func (diagonal matrix))))

```

When computing the diagonal recursively, we check whether `(head matrix)` is truthy. If the matrix is out of rows, it will be the empty list (nil), and `head` of nil is nil--falsey. Or, if the matrix is out of columns, its first row (head) will be the empty list (nil)--falsey. Otherwise, there will be a nonempty first row, which is truthy.

So, if the first row doesn't exist or is empty, we return nil. Otherwise, if there is a nonempty first row, we take `(head (head matrix))`--the first element of the first row--and `cons` (prepend) it to the result of the recursive call. The argument to the recursive call is `(map tail (tail matrix))`--that is, take all rows but the first, and take all but the first element of each row.

# Answer
> 1 votes
# APL NARS, 20 bytes, 10 chars

```
{⍺⍺/1 1⍉⍵}

```

test:

```
  f←{⍺⍺/1 1⍉⍵}
  ⎕←q←3 3⍴⍳10
1 2 3
4 5 6
7 8 9
  ×f q
45
  *f q
1
  {⍺+2×⍵}f q
47
  ⌈f q
9
  {2×⍺+0×⍵}f q
2
  -f ⊃(4 5 6)(1 2 3)
2
  {(⍺+⍵)÷2}f ⊃(2 3 4)(5 6 7)(8 9 10)
5
  ∧f ⊃(2 2 2)(2 2 3)(2 3 3)(4 4 4)
6

```

# Answer
> 0 votes
# Jelly, 5 bytes

Left-to-right.

```
ŒDḢç/

```

Try it online!

**Disclaimer:** I do not know if this an acceptable input method for black-box functions. This assumes that the function is implemented in the link above, and is thus "named" (that is, it's callable with) `ç`, but otherwise I have no way to assign it to `ç`. If anyone has more experience with Jelly + black box functions, I would appreciate thoughts. After spending some time in chat, we figured that using `ç` might indeed be valid.

# Answer
> 0 votes
## Clojure, 30 bytes

```
#(reduce %2(map nth %(range)))

```

Reduces "from the left".

# Answer
> 0 votes
# Husk, 6 bytes

```
F₁►L∂↔

```

Try it online!

takes function in the footer.

Folds from the left.

---
Tags: code-golf, math, matrix, linear-algebra, functional-programming
---


title: Make a Rectangle from a Triangle

text:
# Question
Title: Make a Rectangle from a Triangle
You can depict a triangular number, T(N), by writing one 1 on a line, then two 2's on the line below, then three 3's on the line below that, and so on until N N's. You end up with a triangle of T(N) numbers, hence the name.

For example, T(1) through T(5):

```
1

1
22

1
22
333

1
22
333
4444

1
22
333
4444
55555

```

To keep things nicely formatted we'll use the last digit of the number for N \> 9, so T(11) would be:

```
1
22
333
4444
55555
666666
7777777
88888888
999999999
0000000000
11111111111

```

Now pretend like each row of digits in one of these triangles is a 1-by-something polyomino tile that can be moved and rotated. Call that a row-tile.

For all triangles beyond T(2) it is possible to rearrange its row-tiles into a W×H rectangle where W \> 1 and H \> 1. This is because there are no prime Triangular numbers above N \> 2. So, for N \> 2, we can make a rectangle from a triangle!

(We're ignoring rectangles with a dimension of 1 on one side since those would be trivial by putting every row on one line.)

Here is a possible rectangle arrangement for each of T(3) through T(11). Notice how the pattern could be continued indefinitely since every odd N (except 3) reuses the layout of N - 1.

```
N = 3
333
221

N = 4
44441
33322

N = 5
55555
44441
33322

N = 6
6666661
5555522
4444333

N = 7
7777777
6666661
5555522
4444333

N = 8
888888881
777777722
666666333
555554444

N = 9
999999999
888888881
777777722
666666333
555554444

N = 10
00000000001
99999999922
88888888333
77777774444
66666655555

N = 11
11111111111
00000000001
99999999922
88888888333
77777774444
66666655555

```

However, there are plenty of other ways one could arrange the row-tiles into a rectangle, perhaps with different dimensions or by rotating some row-tiles vertically. For example, these are also perfectly valid:

```
N = 3
13
23
23

N = 4
33312
44442

N = 5
543
543
543
541
522

N = 7
77777776666661
55555444433322

N = 8
888888881223
666666555553
444477777773

N = 11
50000000000
52266666634
57777777134
58888888834
59999999994
11111111111

```

# Challenge

Your task in this challenge is to take in a positive integer N \> 2 and output a rectangle made from the row-tiles of the triangles of T(N), as demonstrated above.

As shown above, remember that:

* The area of the rectangle will be T(N).
* The width and height of the rectangle must both be greater than 1.
* Row-tiles can be rotated horizontally or vertically.
* Every row-tile must be depicted using the last digit of the number it represents.
* Every row-tile must be fully intact and within the bounds of the rectangle.

The output can be a string, 2D array, or matrix, but the numbers must be just digits from 0 through 9.

The output does not need to be deterministic. It's ok if multiple runs produce multiple, valid rectangles.

**The shortest code in bytes wins!**

# Answer
> 18 votes
# Python 2, 59 bytes

```
n=input()
c=~n%2
while c<n:print`n%10`*n+`c%10`*c;n-=1;c+=1

```

Try it online!

Prints like:

```
55555
44441
33322

```

It looks kind-of redundant to update `n-=1;c+=1` where sum `n+c` remains unchanged. I feel like there's a better way, but I haven't seen it so far. Bounty is up for grabs!

---

**60 bytes**

```
n=input()
b=a=n/2
while n-b:b+=1;print`a%10`*a+`b%10`*b;a-=1

```

Try it online!

Prints like:

```
22333
14444
55555

```

Based on ideas by @newbie.

# Answer
> 5 votes
# APL (Dyalog), ~~49~~ ~~47~~ ~~34~~ ~~38~~ 35 bytes

*3 bytes saved thanks to @Bubbler!*

```
{10|(⌈⍵÷2)↑↑,/⍴⍨¨⍉↑((⍳⍵)-2|⍵)(⌽⍳⍵)}

```

Try it online!

```
                  ⍉↑                    ⍝ concat each pair in
                     ((⍳⍵)     )(⌽⍳⍵)   ⍝ 1..n and n..1 (into 2×n matrix)
                          -2|⍵           ⍝ concats n-1..0 if n is odd
               ⍴⍨¨                       ⍝ repeat each item *itself* times
            ↑,/                          ⍝ flatten
     (⌈⍵÷2)↑                             ⍝ take first n/2 rows
10|                                      ⍝ for each item, take the last digit

0 7      7 7 7 7 7 7 7      7 7 7 7 7 7 7
1 6  =>  1 6 6 6 6 6 6  =>  1 6 6 6 6 6 6
2 5      2 2 5 5 5 5 5      2 2 5 5 5 5 5
3 4      3 3 3 4 4 4 4      3 3 3 4 4 4 4
4 3      4 4 4 4 3 3 3
5 2      5 5 5 5 5 2 2
6 1      6 6 6 6 6 6 1

```

# Answer
> 2 votes
# 05AB1E, ~~16~~ ~~15~~ 14 bytes

```
Ýεθy×}2äí`RøJ»

```

Try it online!

# Answer
> 2 votes
# JavaScript (ES8),  ~~72 71~~  68 bytes

Returns a string.

```
n=>(g=k=>k<n?(h=k=>''.padEnd(k,k%10))(k)+h(n--)+`
`+g(k+1):'')(~n&1)

```

Try it online!

# Answer
> 2 votes
# Charcoal, 24 bytes

```
ＮθＥ…÷θ²θ⭆⟦⊕ι⁻｜θ¹⊕ι⟧⭆λ﹪λχ

```

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

```
Ｎθ

```

Input `N`.

```
Ｅ…÷θ²θ

```

Loop rows from `N/2` to `N`. (Due to the increments in the code below, `N/2` is excluded and `N` is included. I could have put the increments here for the same byte count.)

```
⭆⟦⊕ι⁻｜θ¹⊕ι⟧

```

Each row contains two row-tiles, one for the row and one for `N|1` minus the row. (If `N` is odd then this last row-tile is empty.)

```
⭆λ﹪λχ

```

Each row-tile consists of copies of its last digit.

# Answer
> 2 votes
# Java 11, 89 bytes

```
n->{for(int c=~n&1;c<n;)System.out.println((n%10+"").repeat(n--)+(c%10+"").repeat(c++));}

```

Port of *@xnor*'s Python answer, so make sure to upvote him!!

Try it online.

**Explanation:**

```
n->{                            // Method with integer parameter and no return-type
  for(int c=~n&1;               //  Temp-integer `c`, starting at 0 if the input is odd;
                                //  or 1 if even
      c<n;)                     //  Loop as long as this `c` is smaller than the input `n`:
    System.out.println(         //   Print with trailing newline:
      (n%10                     //     The last digit of `n`
           +"")                 //     converted to String
               .repeat(n        //     repeated `n` amount of times
                        --)     //     After which `n` is decreased by 1 with `n--`
      +                         //    Appended with:
       (c%10                    //     The last digit of `c`
            +"")                //     converted to String
                .repeat(c       //     repeated `c` amount of times
                         ++));} //     After which `c` is increased by 1 with `c++`

```

# Answer
> 2 votes
# , ~~41~~ 33 bytes

-8 bytes thanks to Bubbler!

```
10(|-:@##"1~@{.],.|.)2&|@>:}.i.,]

```

Try it online!

# K (oK), ~~41~~ ~~38~~ 32 bytes

-6 bytes thanks to ngn!

```
{(x%2)#10!{x}#'(a-2!x),'|a:1+!x}

```

Try it online!

# Answer
> 2 votes
# Erlang (escript), 109 bytes

Seems huge in comparison with other answers.

```
t(A,B)when A<B->"";t(A,B)->[string:copies([X rem 10+48],X)||X<-[A,B]]++"
"++t(A-1,B+1).
t(N)->t(N,1-N rem 2).

```

Try it online!

# Answer
> 2 votes
# Perl 5 `-n`, 43 bytes

```
@a=map$_%10x$_,$_&1^1..$_;say$_,pop@a for@a

```

Try it online!

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

Saved 3 bytes thanks to newbie!!!

```
i;c;f(n){for(c=-n%2;++c<n;--n,puts(""))for(i=0;i<n+c;)putchar((i++<n?n:c)%10+48);}

```

Try it online!

Port of xnor's Python answer so make sure to upvote him!!!

# Answer
> 1 votes
# Ruby, ~~64~~ 62 bytes

```
->n{c=1&~n;n,c=n-1,-~c,puts("#{n%10}"*n+"#{c%10}"*c)while c<n}

```

Try it online!

Based on @xnor's Python answer, thanks!

# Answer
> 1 votes
# , ~~30~~ 29 bytes

```
10(|-:@#$]#~@,"0|.)2&|0&,1+i.

```

Try it online!

J's reshape `$` is so weird that it works in place of take `{.` when the left is positive singleton (regardless of what comes on the right).

---

# , 30 bytes

```
10(|-:@#{.]#~@,"0|.)2&|0&,1+i.

```

Try it online!

Yet another case of repeat-bind (dyadic `&`) winning over other approaches.

### How it works

```
10(|-:@#{.]#~@,"0|.)2&|0&,1+i.   NB. input=n
                          1+i.   NB. 1..n
                    2&|0&,   NB. prepend 0, but only if n is odd
  (       ]    "0|.)   NB. for each pair (x,y) of the above and above reversed,
           #~@,        NB. concatenate x copies of x and y copies of y
    -:@#{.   NB. take half the rows
10 |         NB. modulo 10 to all elements of the array

```

# Answer
> 1 votes
# APL (Dyalog Unicode), 42 bytes

```
10|{⍵=1:1 1⍴1⋄2|⍵:⍵⍪∇⍵-1⋄(⍳∘≢,1+⊢,⊢/)∇⍵-1}

```

Try it online!

A fresh approach using recursion, though not very short.

### How it works

```
10|{⍵=1:1 1⍴1⋄2|⍵:⍵⍪∇⍵-1⋄(⍳∘≢,1+⊢,⊢/)∇⍵-1}

           ⍝ Input: n
⍵=1:1 1⍴1  ⍝ Base case: If n=1, give a 1x1 matrix of 1

2|⍵:⍵⍪∇⍵-1  ⍝ For odd n, prepend n copies of n on the top

(⍳∘≢,1+⊢,⊢/)∇⍵-1  ⍝ For even n...
       ⊢,⊢/       ⍝ append its own last column to its right
     1+           ⍝ add 1 to all elements
 ⍳∘≢,             ⍝ prepend a column of 1..(number of rows) to its left

10|{...}  ⍝ Apply modulo 10 to all elements

```

# Answer
> 1 votes
# Jelly, 13 bytes

```
_Ḷ€ZŒHṚ;"¥/%⁵

```

A monadic Link accepting an integer which yields a list of lists of integers in \\$\[0,9\]\\$.

**Try it online!** (footer just reformats the output list of lists)

I feel there may be shorter.

### How?

```
_Ḷ€ZŒHṚ;"¥/%⁵ - Link: integer, n
  €           - for each (i) in (implicit range [1..n])
 Ḷ            -   lowered range (i) -> [0..i-1]
_             - (n) subtract (vectorised across that) -> [[n],[n,n-1],...,[n,n-1,...,1]]
   Z          - transpose -> [[n]*n,[n-1]*(n-1),...,[1]]
    ŒH        - split into half (first half longer if n is odd)
          /   - reduce (this list of two lists) by:
         ¥    -   last two links as a dyad:
      Ṛ       -     reverse (the first half)
        "     -     zip together applying:
       ;      -       concatenation
            ⁵ - literal ten
           %  - modulo

```

---

An alternative first three bytes is `rRṚ`

# Answer
> 1 votes
# Husk, 16 bytes

```
←½Ṡz+↔↓¬%2¹m´Rŀ→

```

Try it online!

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

```
(r=#+(y=Mod[#+1,2]);""<>{z@#,z[r-#]}&/@Range@r)[[-⌈r/2⌉;;-y-1]]&
z@x_:=""<>ToString/@Table[x~Mod~10,x]

```

Try it online!

# Answer
> 0 votes
# Icon, 76 bytes

```
procedure f(n)
c:=seq(1-n%2)&write(repl(n%10,n)||repl(c%10,c))&(n-:=1)=c
end

```

Try it online!

Inspired by xnor's Python solution \- don't forget to upvote it!

---
Tags: code-golf, string, math, integer, matrix
---


title: Sum of replicated matrices

text:
# Question
Title: Sum of replicated matrices
Given a list of numbers \\$\[a\_1, a\_2, ... a\_n\]\\$, compute the sum of all the matrices \\$A\_i\\$ where \\$A\_i\\$ is defined as follows (\\$m\\$ is the maximum of all \\$a\_i\\$):

$$ \begin{array}{c|cc} & 1 & 2 & \cdots & i-1 & i & i+1 & \cdots & n \\ \hline 1 & 0 & 0 & \cdots & 0 & a\_i & a\_i & \cdots & a\_i \\ 2 & 0 & 0 & \cdots & 0 & a\_i & a\_i & \cdots & a\_i \\ \vdots & & \vdots & & \vdots & & \vdots & & \vdots \\ a\_i & 0 & 0 & \cdots & 0 & a\_i & a\_i & \cdots & a\_i \\ a\_{i+1}& 0 & 0 & \cdots & 0 & 0 & 0 & \cdots & 0 \\ \vdots & & \vdots & & \vdots & & \vdots & & \vdots \\ m & 0 & 0 & \cdots & 0 & 0 & 0 & \cdots & 0 \\ \end{array} $$

## Example

Given the input `[2,1,3,1]` we construct the following matrix:

$$ \left\[\begin{matrix} 2 & 2 & 2 & 2 \\ 2 & 2 & 2 & 2 \\ 0 & 0 & 0 & 0 \\ \end{matrix}\right\] \+ \left\[\begin{matrix} 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{matrix}\right\] \+ \left\[\begin{matrix} 0 & 0 & 3 & 3 \\ 0 & 0 & 3 & 3 \\ 0 & 0 & 3 & 3 \\ \end{matrix}\right\] \+ \left\[\begin{matrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{matrix}\right\] = \left\[\begin{matrix} 2 & 3 & 6 & 7 \\ 2 & 2 & 5 & 5 \\ 0 & 0 & 3 & 3 \\ \end{matrix}\right\] $$

## Rules and I/O

* you may assume the input is non-empty
* you may assume all the inputs are non-negative (0≤)
* the input can be a \\$1×n\\$ (or \\$n×1\\$) matrix, list, array etc.
* similarly the output can be a matrix, list of lists, array etc.
* you can take and return inputs via any default I/O format
* your submission may be a full program or function

## Test cases

```
[0] -> [] or [[]]
[1] -> [[1]]
[3] -> [[3],[3],[3]]
[2,2] -> [[2,4],[2,4]]
[3,0,0] -> [[3,3,3],[3,3,3],[3,3,3]]
[1,2,3,4,5] -> [[1,3,6,10,15],[0,2,5,9,14],[0,0,3,7,12],[0,0,0,4,9],[0,0,0,0,5]]
[10,1,0,3,7,8] -> [[10,11,11,14,21,29],[10,10,10,13,20,28],[10,10,10,13,20,28],[10,10,10,10,17,25],[10,10,10,10,17,25],[10,10,10,10,17,25],[10,10,10,10,17,25],[10,10,10,10,10,18],[10,10,10,10,10,10],[10,10,10,10,10,10]]

```

# Answer
> 11 votes
# Jelly, ~~10~~ 5 bytes

```
ẋ"z0Ä

```

Try it online!

### How it works

```
ẋ"z0Ä  Main link. Argument: A (array)

       e.g. [2, 1, 3, 1]

ẋ"     Repeat each n in A n times.

       e.g. [[2, 2   ]
             [1      ]
             [3, 3, 3]
             [1      ]]

  z0   Zipfill 0; read the result by columns, filling missing elements with 0's.

        e.g. [[2, 1, 3, 1]
              [2, 0, 3, 0]
              [0, 0, 3, 0]]

    Ä  Take the cumulative sum of each row vector.

       e.g. [[2, 3, 6, 7]
             [2, 2, 5, 5]
             [0, 0, 3, 3]]

```

# Answer
> 4 votes
# , 80 bytes

```
n=sum((a=scan())|1);for(i in 1:n)F=F+`[<-`(matrix(0,max(a),n),0:a[i],i:n,a[i]);F

```

Try it online!

Takes input from stdin; prints a `0x1` matrix for input `0`, which prints out like

```
	[,1]
```

# Answer
> 4 votes
# Haskell, ~~70~~ ~~66~~ 51 bytes

```
g x=[scanl1(+)[sum[n|n>=r]|n<-x]|r<-[1..maximum x]]

```

Try it online!

# Answer
> 4 votes
# APL (Dyalog Unicode), 8 bytesSBCS

Full program. Prompts stdin for list, prints matrix to stdout.

Uses Dennis's method.

```
+\⍉↑⍴⍨¨⎕

```

Try it online!

stdin

`⍴⍨¨`**r**eshape-selfie of each

mix list of lists into matrix, filling with 0s

transpose

`+\` cumulative row-wise sum

The  doesn't make any computational difference, so it could potentially be left out and `\` changed to  to sum column-wise instead of row-wise.

# Answer
> 3 votes
# JavaScript (ES6), ~~88~~ 79 bytes

Returns `[]` for `[0]`.

```
f=(a,y,b=a.map((_,x)=>a.map(c=>y>=c|x--<0?0:s+=c,s=0)|s))=>s?[b,...f(a,-~y)]:[]

```

Try it online!

# Answer
> 2 votes
# Python 2, 85 bytes

```
lambda x:[[sum(n*(n>j)for n in x[:i+1])for i in range(len(x))]for j in range(max(x))]

```

Try it online!

# Answer
> 2 votes
# Octave, 64 bytes

```
@(x,k=a=0*(x+(1:max(x))'))eval"for i=x;a(1:i,++k:end)+=i;end,a";

```

Try it online!

### Explanation:

Yet again: Expressions in the argument list and eval are used in one function :)

This takes `x` as input, and creates two identical matrices filled with zeros, with the dimensions `k=a=zeros(length(x),max(x))`. This is achieved by adding the horizontal vector `x` with a vertical vector with `1:max(x)`, implicitly expanding the dimensions to a 2D-array, then multiplying this with zero. `~(x+...)` doesn't work unfortunately, since that forces `a` to be a logical array throughout the rest of the function.

`for i=x` is a loop that for each iteration makes `i=x(1)`, then `i=x(2)` and so on. `a(1:i,k++:end)` is the part of the matrix that should be updated for each iteration. `1:i` is a vector saying which rows should be updated. If `i=0`, then this will be an empty vector, thus nothing will be updated, otherwise it's `1, 2 ...`. `++k:end` increments the `k` matrix by one, and creates a range from the first value of this matrix (`1,2,3...`) and up to the last column of the `a` matrix. `+=i` adds the current value to `a`. `end,a` ends the loop and outputs `a`.

# Answer
> 2 votes
# Wolfram Language (Mathematica), 42 bytes

```
Thread@Accumulate@PadRight[#~Table~#&/@#]&

```

Try it online!

# Answer
> 2 votes
# Java 10, ~~142~~ ~~135~~ 134 bytes

```
a->{int l=a.length,i=0,j,s,m=0;for(int q:a)m=q>m?q:m;int[][]r=new int[m][l];for(;i<m;i++)for(j=s=0;j<l;j++)r[i][j]=s+=i<a[j]?a[j]:0;return r;}

```

-7 bytes thanks to *@ceilingcat*.

Try it online.

```
a->{              // Method with integer-array parameter and integer-matrix return-type
  int l=a.length, //  Length of the input-array
      i,j,        //  Index integers
      s,          //  Sum integer
  m=0;for(int q:a)m=q>m?q:m;
                  //  Determine the maximum of the input-array
  var r=new int[m][l];
                  //  Result-matrix of size `m` by `l`
  for(;m-->0;)    //  Loop `i` over the rows
    for(j=s=0;    //   Reset the sum to 0
        j<l;j++)  //   Inner loop `j` over the columns
      r[m][j]=s+= //    Add the following to the sum `s`, add set it as current cell:
        m<a[j]?   //     If the row-index is smaller than the `j`'th value in the input:
         a[j]     //      Add the current item to the sum
        :         //     Else:
         0;       //      Leave the sum the same by adding 0
  return r;}      //  Return the result-matrix

```

# Answer
> 1 votes
# GolfScript, 39 bytes

```
{.$):M;;{[.](*[0]M*+M<}%zip{{\.@+}*]}%}

```

Try it online!

Uses Dennis's algorithm.

# Answer
> 1 votes
# Ruby, 50 bytes

```
->a{(1..a.max).map{|n|w=0;a.map{|r|w+=(r<n)?0:r}}}

```

Try it online!

# Answer
> 1 votes
# Pari/GP, 60 bytes

```
a->matrix(vecmax(a),#a,i,j,vecsum([a[k]|k<-[1..j],a[k]>=i]))

```

Try it online!

# Answer
> 0 votes
# Japt, 10 bytes

```
ÔËÆD
z ®å+

```

Try it (includes all test cases)

# Answer
> 0 votes
# Husk, 7 bytes

```
m∫T0m´R

```

Try it online!

Dennis' method.

# Answer
> 0 votes
# k, 24 Bytes

```
{+\'+(x#'x),'(x-|/x)#'0}

```

Dennis algorithm

## Sample

```
  {+\'+(x#'x),'(x-|/x)#'0}2 1 3 1
(2 3 6 7;2 2 5 5;0 0 3 3)

```

numeric arrays in k are represented as a sequence of values without separators, so `2 1 3 1` is the same as `[2,1,3,1]` in other languages.

k Use the syntax `(..;..;..)` to represent an heterogeneous or multi-level list, so `(2 3 6 7;2 2 5 5;0 0 3 3)` is the same as `[[2,3,6,7],[2,2,5,5],[0,0,3,3]]` in other languages

## Explanation

* `{..x..}` defines an anobymous function with implicit arg x
* `+\array` is the cummulative sum of the elems of the array
* `f'matrix` applies f to each row ('=each) of the matrix preserving matrix shape, so `+\'matrix` calculates cummulative sum of the elems of each row of the matrix
* `n#x` signifies take n copies of x value. if n and x are both arryas of the same length, `n#'x` applies `#` to each pair, so `2 1 3 1#'2 1 3 1` is the same as `(2#2; 1#1; 3#3; 1#1)` and evaluates to `(2 2;,1;3 3 3;,1)`. NOTE one-item list is represented as `,item`
* `a,b` joins (catenates) arrays a and b. `a,'b` applies `,` to each corresponding items of a and b: if both are matrices of the same shape, catenates each corresponding pair of rows
* `|/array` applies binary operator `|` (max) over the elements of the array (reduce), so `|/2 1 3 1` is equivalent to `2|1|3|1` and reduces to 3
* `(x-|/x)` substract to each element of x the maximum of the array, so `2 1 3 1 - |/2 1 3 1` is the same as `2 1 3 1 - 3` and evaluate to `-1 -2 0 -2`
* `array#'0` is "take n copies of 0" for each value n in array. It really uses "abs(n) take 0", so we don't worry about sign. `-1 -2 0 -2#'0` evaluates to `(,0;0 0;();0 0)`. NOTE.- `()` is the empty array

k applies unary operators and binary operators right to left, and parenthesis indicate precedence. NOTE.- k uses one-letter symbols, with two meanings (unary op or binary op) depending of context (example `+` as binary op is sum, but as unary op is flip (transpose).

* `#'` is a binary op modified by `'` adverb. Its arguments are `(x-|/x)` and `0`.
    + Evaluates `x-|/x` first. `|` it's a binary op (max), but adverb `/` convert it to unary (max over x), and evaluates to `3`. The resulting `x-3` is a binary op (minus), with args `x`and `3`, and evals to `-1 -2 0 -2`
    + `-1 -2 0 -2#'0` evals to `(,0;0 0;();0 0)`
* The actual expr is `+\'+(x#'x),'(,0;0 0;();0 0)`. `,` is a binary op (join) modified by `'` adverb (each): we need to evaluate the left arg `(x#'x)`
    + `x#'x` is `2 1 3 1#'2 1 3 1`, and applies binay op `#` (take) to each pair. The result is `(2 2;,1;3 3 3;,1)`
    + `(2 2;,1;3 3 3;,1),'(,0;0 0;();0 0)` applies binary op `,` modified by (') each, and join each pair of corresponding values. The result is `(2 2 0;1 0 0;3 3 3;1 0 0)`
* `+` is a monad operator that transpose (flip) the matrix, so the result is `(2 1 3 1;2 0 3 0;0 0 3 0)`
* `+\'matrix` calculates cummulative sums of each row of the matrix, so eval to \`(2 3 6 7;2 2 5 5;0 0 3 3)

---
Tags: code-golf, math, array, matrix
---


title: Find Primes in Pi

text:
# Question
Title: Find Primes in Pi
# Primes are everywhere...

they hide inside Pi

3.141592653**58979**3238**462643**3832**795028841**971693993751

Let's get those primes!

# The Challenge

Given as input an integer `n>0`, find out how many primes are hidden inside the first `n` digits of `Pi`

# Examples

For `n=3` we should search for primes in `[3,1,4]`. There are 2 Primes `(3,31)`, so your code should output `2`
For `n=10` , the first 10 digits are `[3,1,4,1,5,9,2,6,5,3]` and your code should output `12` because `[2, 3, 5, 31, 41, 53, 59, 653, 4159, 14159, 314159, 1592653]` were hidden (and found!)

# Test Cases

input -\> output

```
1->1
3->2
13->14
22->28
42->60
50->93

150->197
250->363
500->895

```

# Rules

Your code must be able to **find all primes at least for `n=50`**
Yes, you can **hardcode the first 50 digits** of `Pi` if you like
**Entries hardcoding the answers are invalid**

This is .Shortest answer in bytes wins!

# Answer
# 05AB1E,  ~~10~~  8 bytes

-2 bytes thanks to Adnan (`p` vectorises)

```
<žsþŒÙpO

```

**Try it online!** (will work up to n=98413 but will be very slow even for n=50 due to the need to test such large numbers for primality - TIO times out at 60 seconds for n=50.)

### How?

```
<žsþŒÙpO - implicitly push input, n
<        - decrement = n-1
 žs      - pi to that many decimal places (i.e. to n digits)
   þ     - only the digits (get rid of the decimal point)
    Œ    - all sublists
     Ù   - unique values
      p  - is prime? (vectorises) 1 if so, 0 otherwise
       O - sum
         - implicitly print the top of the stack

```
> 20 votes

# Answer
# Mathematica, 76 bytes

```
Tr[1^Union@Select[FromDigits/@Subsequences@#&@@RealDigits[Pi,10,#],PrimeQ]]&

```
> 11 votes

# Answer
# Mathematica, ~~104~~ ~~97~~ 90 bytes

```
Length@DeleteDuplicates@Select[FromDigits/@Subsequences@First@RealDigits[Pi,10,#],PrimeQ]&

```

Hahahaha, I managed to make this work. I have no idea how to use Mathematica. XD

Input:

```
[50]

```
> 6 votes

# Answer
# Python 3, ~~274~~ ~~237~~ ~~207~~ ~~194~~ 189 bytes

*-37 bytes thanks to Wheat Wizard! -14 bytes thanks to Mr.Xcoder.*

Hardcodes the first 50 digits of *pi* but manually computes everything else.

```
x=int(input());l="31415926535897932384626433832795028841971693993751"[:x]
print(sum(all(i%m for m in range(2,i))for i in{int(i)for w in range(x)for i in[l[j:j-~w]for j in range(x-w)]}-{1}))

```

Try it online!
> 3 votes

# Answer
# R, ~~156~~ 123 bytes

```
cat(cumsum(c(1,1,0,1,1,4,1,0,0,3,0,0,2,7,3,1,0,3,0,0,0,0,0,0,4,1,0,6,0,3,2,0,0,0,0,0,0,4,3,3,6,0,4,8,2,5,3,6,0,5))[scan()])

```

Super interesting solution. Working on a proper one.

Saved 33 bytes thanks to @Giuseppe.

# R (+ numbers and gmp), 198 bytes

```
function(n,x=unique(gmp::as.bigz(unlist(sapply(1:n,function(x)substring(gsub("[.]","",numbers::dropletPi(50)),x,x:n))))))min(length(x),sum(sapply(sapply(x[x>0&!is.na(x)],gmp::factorize),length)==1))

```

Proper solution. Takes `n` as input.

Uses `numbers::dropletPi(50)` to generate the first 50 decimal places of pi. `gsub` removes the decimal point. `substring` takes every possible substring (surprise surprise) of pi up to `n`.

The returned list is flattened and converted to `gmp`'s `bigz` format. This format is required to store integers of length 50. `unique` takes the unique values of that vector. This result gets stored in `x`.

Then we check for primality. This is tricky, because there are a bunch of edge-cases and annoyances:

* For high `n`, there is a `0` in pi. This leads to substrings with a leading zero. `as.bigz` produces `NA`s with that, which have to be removed.
* On a similar note, the substring `"0"` will crash `gmp::factorize`, so has to be removed as well.
* For `n=1`, `x = 3`. Which in itself is ok, but the `bigz` representation of `3` is iterable, so `sapply` will get confused and report 16 primes. To this end we take the minimum of the length of the vector `x`, and the amount of primes in it.
* `gmp::isprime` can't seem to reliably handle the large numbers reliably. So instead we use `gmp::factorize` and check of the length of the output is 1.

So in all, we remove `0` and `NA` from `x`. We factorize all of `x` and check for the length. We count the number of occurrences of `1` and return the `min(occurences, length(x))`.
> 1 votes

# Answer
# Jelly, ~~59~~ 32 bytes

*-27 bytes thanks to Erik the Outgolfer.*

```
“!⁶⁷¬,6½ạEC.wʠ€Ẉ!+Ẉfṭ¡’Ṿḣ³ẆVQÆPS

```

Try it online!

## Explanation

```
“...’Ṿḣ³ẆVQÆPS

“...’           compressed string that evaluates to first 50 digits of pi (314159...)
     Ṿ          uneval; stringify
      ḣ³        first n characters of the string where n is the first command-line argument
        Ẇ       all sublists
         V      convert all elements to integers
          Q     deduplicate
           ÆP   convert all prime elements to 1 and others to 0
             S  sum

```
> 1 votes

# Answer
# Husk, 9 bytes

```
#ṗumdQ↑İπ

```

Try it online!

Freezes beyond n=10 on tio. Reverse of the 05AB1E program.
> 1 votes

---
Tags: code-golf, math, primes, pi
---