title: Sum \$\text{Square}^2\$

text:
# Question
Title: Sum \$\text{Square}^2\$
Let \\$n=42\\$ (Input)

Then divisors are : 1, 2, 3, 6, 7, 14, 21, 42

Squaring each divisor : 1, 4, 9, 36, 49, 196, 441, 1764

Taking sum (adding) : 2500

Since \\$50\times 50=2500\\$ therefore we return a truthy value. If it is not a perfect square, return a falsy value.

# Examples :

```
42  ---> true
1   ---> true
246 ---> true
10  ---> false
16  ---> false

```

This is so shortest code in bytes for each language wins

Thanks to @Arnauld for pointing out the sequence : A046655

# Answer
# , ~~39~~ 37 bytes

```
!sum((y=1:(x=scan()))[!x%%y]^2)^.5%%1

```

Try it online!

Uses the classic "test if perfect square" approach, taking the non-integral part of the square root `S^.5%%1` and taking the logical negation of it, as it maps zero (perfect square) to `TRUE` and nonzero to `FALSE`.

Thanks to Robert S for saving a couple of bytes!
> 6 votes

# Answer
# JavaScript (ES7),  ~~46 44~~  42 bytes

*Saved 1 byte thanks to @Hedi*

```
n=>!((g=d=>d&&d*d*!(n%d)+g(d-1))(n)**.5%1)

```

Try it online!

## Commented

```
n =>             // n = input
  !(             // we will eventually convert the result to a Boolean
    (g = d =>    // g is a recursive function taking the current divisor d
      d &&       //   if d is equal to 0, stop recursion
      d * d      //   otherwise, compute d²
      * !(n % d) //   add it to the result if d is a divisor of n
      + g(d - 1) //   add the result of a recursive call with the next divisor
    )(n)         // initial call to g with d = n
    ** .5 % 1    // test whether the output of g is a perfect square
  )              // return true if it is or false otherwise

```
> 5 votes

# Answer
# 05AB1E, 5 bytes

```
ÑnOÅ²

```

**Try it online!**

### How?

```
ÑnOÅ²
Ñ     - divisors
 n    - square
  O   - sum
   Å² - is square?

```
> 5 votes

# Answer
# Shakespeare Programming Language, ~~434~~ ~~428~~ 415 bytes

```
,.Ajax,.Ford,.Puck,.Act I:.Scene I:.[Enter Ajax and Ford]Ford:Listen tothy.Scene V:.Ajax:You be the sum ofyou a cat.Ford:Is the remainder of the quotient betweenyou I worse a cat?[Exit Ajax][Enter Puck]Ford:If soyou be the sum ofyou the square ofI.[Exit Puck][Enter Ajax]Ford:Be you nicer I?If solet usScene V.[Exit Ford][Enter Puck]Puck:Is the square ofthe square root ofI worse I?You zero.If notyou cat.Open heart

```

Try it online!

*-13 bytes thanks to Jo King!*

Outputs `1` for true result, outputs `0` for false result.
> 5 votes

# Answer
# Python 2, 55 bytes

```
lambda n:sum(i*i*(n%i<1)for i in range(1,n+1))**.5%1==0

```

Try it online!
> 4 votes

# Answer
# C (gcc), ~~67~~ ~~63~~ ~~60~~ 59 bytes

*-1 bytes* thanks to @JonathanFrech

```
i,s;f(n){for(s=i=0;i++<n;)s+=n%i?0:i*i;n=sqrt(s);n=n*n==s;}

```

Try it online!
> 3 votes

# Answer
# Neim, 5 bytes

```
ᛦq

```

Explanation:

```
      Factors
 ᛦ      Squared
       Summed
       is in?
   q    infinite list of square numbers

```

Try it online!
> 3 votes

# Answer
# Brachylog, ~~12~~ 8 bytes

```
f^₂ᵐ+~^₂

```

-4 bytes thanks to Fatelize cause i didn't realize brachylog has a factors functions

# explanation

```
f^₂ᵐ+~^₂            #   full code
f                   #       get divisors
 ^₂ᵐ                #           square each one
    +               #       added together
      ~^₂           #       is the result of squaring a number

```

Try it online!
> 3 votes

# Answer
# MathGolf, ~~5~~ 4 bytes

```
─²Σ°

```

Try it online!

## Explanation

```
─     Get all divisors as list (implicit input)
 ²    Square (implicit map)
  Σ   Sum
   °  Is perfect square?

```

Very similar to other answers, compared to 05AB1E I gain one byte for my "is perfect square" operator.
> 3 votes

# Answer
# MATL, 9 bytes

```
Z\UsX^tk=

```

Try it online!

As simple as it gets

```
Z\ % Divisors of (implicit) input
U  % Square
s  % Sum
X^ % Square root
t  % Duplicate this value
k= % Is it equal to its rounded value?

```
> 3 votes

# Answer
# Thunno 2, 5 bytes

```
F²SÆ²

```

Try it online!

#### Explanation

```
F²SÆ²  # Implicit input
F      # Factors
 ²     # Square
  S    # Sum
   Æ²  # Perfect square
       # Implicit output

```
> 3 votes

# Answer
# Japt, ~~11~~ ~~9~~ 7 bytes

*-2 bytes from @Giuseppe and another -2 from @Shaggy*

```
â x²¬v1

```

---

```
â x²¬v1             Full program. Implicity input U
â                   get all integer divisors of U
  x²                square each element and sum
    ¬               square root result
     v1           return true if divisible by 1

```

Try it online!
> 2 votes

# Answer
## Matlab, 39 37 bytes

```
@(v)~mod(sqrt(sum(divisors(v).^2)),1)

```

Unfortunately, it doesn't work on Octave (on tio) so no tio link.

**Note** As @LuisMendo stated, `divisors()` belongs to Symbolic Toolbox.
> 2 votes

# Answer
# PowerShell, ~~68~~ 56 bytes

```
param($n)1..$n|%{$a+=$_*$_*!($n%$_)};1..$a|?{$_*$_-eq$a}

```

Try it online!

~~Seems long ...~~
*-12 bytes thanks to mazzy*

Does exactly what it says on the tin. Takes the range from `1` to input `$n` and multiplies out the square `$_*$_` times whether it's a divisor or not `!($n%$_)`. This makes divisors equal to a nonzero number and non-divisors equal to zero. We then take the sum of them with our accumulator `$a`. Next, we loop again from `1` up to `$a` and pull out those numbers where `|?{...}` it squared is `-eq`ual to `$a`. That is left on the pipeline and output is implicit.

Outputs a positive integer for truthy, and nothing for falsey.
> 2 votes

# Answer
# K (oK), ~~26~~ ~~25~~ 22 bytes

**Solution:**

```
{~1!%+/x*x*~1!x%:1+!x}

```

Try it online!

**Explanation:**

```
{~1!%+/x*x*~1!x%:1+!x} / the solution
{                    } / lambda taking x as input
                   !x  / range 0..x-1                        \
                 1+    / add 1                               |
              x%:      / x divided by and save result into x |
            1!         / modulo 1                            | get divisors
           ~           / not                                 |
         x*            / multiply by x                       /
       x*              / multiply by x (aka square)          > square
     +/                / sum up                              > sum up
    %                  / square root                         \
  1!                   / modulo 1                            | check if a square
 ~                     / not                                 /

```

**Notes:**

* -1 bytes taking inspiration from the PowerShell solution
* -3 bytes taking inspiration from the APL solution
> 2 votes

# Answer
# APL (Dyalog Unicode), 18 bytes

```
0=1|.5*⍨2+.*⍨∘∪⍳∨⊢

```

Try it online!

Anonymous lambda. Returns 1 for truthy and 0 for falsy (test cases in TIO are prettified).

Shoutouts to @H.PWiz for 4 bytes!

### How:

```
0=1|.5*⍨2+.*⍨∘∪⍳∨⊢   ⍝ Main function, argument ⍵ → 42
                ∨⊢   ⍝ Greatest common divisor (∨) between ⍵ (⊢)
               ⍳      ⍝ and the range (⍳) [1..⍵]
              ∪      ⍝ Get the unique items (all the divisors of 42; 1 2 3 6 7 14 21 42)
             ∘        ⍝ Then
            ⍨         ⍝ Swap arguments of
        2+.*          ⍝ dot product (.) of sum (+) and power (*) between the list and 2
                      ⍝ (sums the result of each element in the vector squared)
       ⍨              ⍝ Use the result vector as base
    .5*               ⍝ Take the square root
  1|                  ⍝ Modulo 1
0=                    ⍝ Equals 0

```
> 2 votes

# Answer
# Pyt, 7 bytes

```
ð²ƩĐř²∈

```

Try it online!

### Explanation

```
            Implicit input
ð           Get list of divisors
 ²          Square each element
  Ʃ         Sum the list [n]
   Đ        Duplicate the top of the stack
    ř²      Push the first n square numbers
      ∈     Is n in the list of square numbers?
            Implicit output

```

---

```
ð²Ʃ√ĐƖ=

```

Try it online!

### Explanation

```
            Implicit input
ð           Get list of divisors
 ²          Square each element
  Ʃ         Sum the list [n]
   √        Take the square root of n
    Đ       Duplicate the top of the stack
     Ɩ      Cast to an integer
      =     Are the top two elements on the stack equal to each other?
            Implicit output

```

---

```
ð²Ʃ√1%¬

```

Try it online!

### Explanation

```
            Implicit input
ð           Get list of divisors
 ²          Square each element
  Ʃ         Sum the list [n]
   √        Take the square root of n
    1%      Take the square root of n modulo 1
      ¬     Negate [python typecasting ftw :)]
            Implicit output

```
> 2 votes

# Answer
# Haskell, ~~78~~ ~~64~~ 53 bytes

*-14 bytes thanks to Ørjan Johansen. -11 bytes thanks to ovs.*

```
f x=sum[i^2|i<-[1..x],x`mod`i<1]`elem`map(^2)[1..x^2]

```

Try it online!

Hey, it's been a while since I've... written *any* code, so my Haskell and golfing might a bit rusty. I forgot the troublesome Haskell numeric types. :P
> 2 votes

# Answer
# Pari/GP, 23 bytes

```
n->issquare(sigma(n,2))

```

Try it online!
> 2 votes

# Answer
# Taxi, ~~4430~~ 4305 bytes

```
Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 1 r.Pickup a passenger going to Cyclone.0 is waiting at Starchild Numerology.0 is waiting at Starchild Numerology.Go to Starchild Numerology:n 1 l 1 l 1 l 2 l.Pickup a passenger going to Rob's Rest.Pickup a passenger going to Addition Alley.Go to Rob's Rest:w 1 r 2 l 1 r.Go to Cyclone:s 1 l 1 l 2 l.[B]Pickup a passenger going to Divide and Conquer.1 is waiting at Starchild Numerology.Go to Starchild Numerology:n 1 r 3 l.Pickup a passenger going to Addition Alley.Go to Addition Alley:w 1 r 3 r 1 r 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l.Pickup a passenger going to Sunny Skies Park.Pickup a passenger going to Divide and Conquer.Go to Divide and Conquer:n 2 r 2 r 1 r.Pickup a passenger going to Cyclone.Go to Sunny Skies Park:e 1 l 1 l 2 l 1 l.Go to Zoom Zoom:n 1 r.Go to Cyclone:w.Pickup a passenger going to Sunny Skies Park.Pickup a passenger going to Equal's Corner.Pickup a passenger going to Trunkers.Go to Sunny Skies Park:n 1 r.Go to Trunkers:s 1 l.Pickup a passenger going to Equal's Corner.Go to Equal's Corner:w 1 l.Switch to plan C if no one is waiting.Pickup a passenger going to Riverview Bridge.Go to Sunny Skies Park:n.Pickup a passenger going to Sunny Skies Park.Pickup a passenger going to Cyclone.Go to Riverview Bridge:n 1 r 1 r.Go to Cyclone:w 2 l.Pickup a passenger going to Cyclone.Go to Sunny Skies Park:n 1 r.Go to Cyclone:n 1 l.Pickup a passenger going to Multiplication Station.Pickup a passenger going to Multiplication Station.Go to Multiplication Station:s 1 l 2 r 4 l.Pickup a passenger going to Addition Alley.Go to Rob's Rest:s 1 r 2 l 1 l 1 r 1 r.Pickup a passenger going to Addition Alley.Go to Addition Alley:s 1 l 1 l 2 r 1 r 1 r.Pickup a passenger going to Rob's Rest.Go to Rob's Rest:n 1 l 1 l 1 l 2 r 1 r.Go to Cyclone:s 1 l 1 l 2 l.Pickup a passenger going to Magic Eight.Go to Sunny Skies Park:n 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l.Pickup a passenger going to Cyclone.Pickup a passenger going to Magic Eight.Go to Magic Eight:s 1 l 2 r.Switch to plan D if no one is waiting.Pickup a passenger going to Addition Alley.Go to Cyclone:n 1 l 2 r.Switch to plan B.[C]Go to Sunny Skies Park:n.Pickup a passenger going to Cyclone.Pickup a passenger going to Addition Alley.Go to Cyclone:n 1 l.Switch to plan B.[D]Go to Cyclone:n 1 l 2 r.Pickup a passenger going to Sunny Skies Park.Pickup a passenger going to Sunny Skies Park.Go to Sunny Skies Park:n 1 r.Go to Rob's Rest:s 2 r 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:s 1 l 1 l 2 l.Pickup a passenger going to Cyclone.Pickup a passenger going to Cyclone.Go to Zoom Zoom:n.Go to Cyclone:w.[E]Pickup a passenger going to Joyless Park.Pickup a passenger going to Divide and Conquer.Go to Joyless Park:n 2 r 2 r 2 l.Go to Cyclone:w 1 r 2 l 2 l.Pickup a passenger going to Cyclone.Pickup a passenger going to Joyless Park.Go to Joyless Park:n 2 r 2 r 2 l.Go to Cyclone:w 1 r 2 l 2 l.Pickup a passenger going to Divide and Conquer.Pickup a passenger going to Divide and Conquer.Go to Divide and Conquer:n 2 r 2 r 1 r.Pickup a passenger going to Magic Eight.1 is waiting at Starchild Numerology.Go to Starchild Numerology:e 1 r 3 r 1 l 1 l 2 l.Pickup a passenger going to Magic Eight.Go to Magic Eight:w 1 r 2 r 1 r.Switch to plan F if no one is waiting.Pickup a passenger going to Riverview Bridge.Go to Joyless Park:e 2 l 4 r.Pickup a passenger going to Cyclone.Pickup a passenger going to The Underground.Go to The Underground:w 1 l.Pickup a passenger going to Cyclone.Go to Fueler Up:s.Go to Riverview Bridge:n 3 l.Go to Cyclone:w 2 l.Switch to plan E.[F]Go to Joyless Park:e 2 l 4 r.Pickup a passenger going to What's The Difference.Pickup a passenger going to Cyclone.Go to Cyclone:w 1 r 2 l 2 l.Pickup a passenger going to Multiplication Station.Pickup a passenger going to Multiplication Station.Go to Multiplication Station:s 1 l 2 r 4 l.Pickup a passenger going to What's The Difference.Go to What's The Difference:n 2 l 1 r 3 l.Pickup a passenger going to Knots Landing.Go to Knots Landing:e 4 r 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:w 1 l.Pickup a passenger going to Post Office.Go to Post Office:n 1 l 1 r.

```

Try it online!

I went to a lot of places in Townsburg that I've never visited before for this program. Because this program is HUGE (mainly due to the fact that there isn't a one-stop way to take square roots; I still don't actually do that, though), I'm going to attempt to sketch out an explanation of this program.

```
Go to Post Office:w 1 l 1 r 1 l.

[Take an input line from STDIN.]

Pickup a passenger going to The Babelfishery.
Go to The Babelfishery:s 1 l 1 r.

[Take it to The Babelfishery, which converts the string to a double.]
[If you were to give it a double, it gives back a string.]

Pickup a passenger going to Cyclone.

[We're going to clone this number by sending it to the Cyclone.]

0 is waiting at Starchild Numerology.

[In Taxi, numeric passengers are introduced once they wait at Starchild Numerology.]
[This passenger will be our running squares total.]

0 is waiting at Starchild Numerology.

[This passenger will be our counter, going from 1 to the inputted number.]
[Yes, it's starting at 0 here, but it is incremented at the start of our loop.]

Go to Starchild Numerology:n 1 l 1 l 1 l 2 l.
Pickup a passenger going to Rob's Rest.
Pickup a passenger going to Addition Alley.
Go to Rob's Rest:w 1 r 2 l 1 r.
Go to Cyclone:s 1 l 1 l 2 l.

[Drop off the squares total at Rob's Rest. We'll pick it back up later when we need it.]
[Also, do the actual cloning of the inputted number.]

[At the start of each loop, our only passenger is the counter, going to Addition Alley.]

[B]
Pickup a passenger going to Divide and Conquer.

[Pick up one of the clones of the inputted number.]
[We will leave the other clone here for later.]

1 is waiting at Starchild Numerology.
Go to Starchild Numerology:n 1 r 3 l.
Pickup a passenger going to Addition Alley.
Go to Addition Alley:w 1 r 3 r 1 r 1 r.
Pickup a passenger going to Cyclone.

[Pick up the number 1, and add it to the counter, then pick up the result.]
[This new passenger is our new counter.]

Go to Cyclone:n 1 l 1 l.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to Divide and Conquer.

[First we pick up the other clone of the inputted number, going to Sunny Skies Park.]
[Sunny Skies Park is basically a First-In-First-Out queue, where we will stick it for later.]
[Then we pick up a clone of the counter which we just dropped off, so we can divide the input by it.]
[We will leave the other clone here for later.]

Go to Divide and Conquer:n 2 r 2 r 1 r.
Pickup a passenger going to Cyclone.

[Divide the inputted number by the counter, and prepare to clone it.]

Go to Sunny Skies Park:e 1 l 1 l 2 l 1 l.

[Drop off our clone of the inputted number at Sunny Skies Park.]

Go to Zoom Zoom:n 1 r.

[Can't forget to get gas!]
[Zoom Zoom is a close gas station, and we have so many credits that one stop here every iteration fills us up completely.]

Go to Cyclone:w.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to Equal's Corner.
Pickup a passenger going to Trunkers.

[First we pick up the other clone of the counter, going to Sunny Skies Park for later.]
[Then we pick up a clone of the division result, going to Equal's Corner.]
[Equal's Corner takes multiple numeric passengers, and returns the value of one of them if they are equal, but otherwise it returns no one.]
[Finally we pick up the other clone of the division result, going to Trunkers.]
[Dropping off a passenger at Trunkers is equivalent to the floor function. We need it here because division results are "exact".]
[(Well, as exact as double precision arithmetic can be.)]
[We will compare the result of this to the exact result of the division.]

Go to Sunny Skies Park:n 1 r.

[Drop off our clone of the counter at Sunny Skies Park.]

Go to Trunkers:s 1 l.
Pickup a passenger going to Equal's Corner.
Go to Equal's Corner:w 1 l.

[Compare the exact division result with the floored division result.]
[If they are equal, then the value of one of them will be waiting.]
[This also means that the counter is a divisor of the input, and we should add the square of the counter to our running squares total.]
[If they are not equal, no one will be waiting, the counter is not a divisor of the input, and nothing should happen.]

Switch to plan C if no one is waiting.

[This is Taxi's only conditional operator.]
[It jumps to a bracketed label (in this case, C) if there is no one waiting at this stop.]
[Of course, there is an unconditional version of this, too.]

[If we are on this path, we are adding the square of the counter to our running squares total.]

Pickup a passenger going to Riverview Bridge.

[We don't actually need the passenger that's waiting here (and leaving it there will not work at all).]
[So what do you do when you have a pesky passenger you don't want? You take them to Riverview Bridge!]
[Riverview Bridge has a lovely view, but passengers dropped off there always seem to fall in the river.]
[This means you don't collect your fare for bringing them there, but at least the pesky passenger is gone.]

Go to Sunny Skies Park:n.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to Cyclone.

[We want to pick up the counter (so we can multiply it by itself). That dang input is in the way, but we still need it.]
[So what do we do? We just take it back to where it was waiting!]
[Yup, even though one would never do this in real life, a passenger's current location is a perfectly legal destination in Taxi.]

Go to Riverview Bridge:n 1 r 1 r.

[So long, Equal's Corner result!]

Go to Cyclone:w 2 l.
Pickup a passenger going to Cyclone.
Go to Sunny Skies Park:n 1 r.

[We clone the counter so we can still use it, then we drop the inputted number back at Sunny Side Park.]
[Again, we will leave the other clone here for later.]

Go to Cyclone:n 1 l.
Pickup a passenger going to Multiplication Station.
Pickup a passenger going to Multiplication Station.
Go to Multiplication Station:s 1 l 2 r 4 l.

[Square the counter.]

Pickup a passenger going to Addition Alley.
Go to Rob's Rest:s 1 r 2 l 1 l 1 r 1 r.
Pickup a passenger going to Addition Alley.
Go to Addition Alley:s 1 l 1 l 2 r 1 r 1 r.
Pickup a passenger going to Rob's Rest.
Go to Rob's Rest:n 1 l 1 l 1 l 2 r 1 r.

[Pick up the running squares total from Rob's Rest, add it to the square of the counter, then bring it back.]

Go to Cyclone:s 1 l 1 l 2 l.
Pickup a passenger going to Magic Eight.

[Pick up the counter, going to Magic Eight.]
[Magic Eight takes two numeric passengers, and returns the first passenger if it is less than the second, but otherwise it returns no one.]
[We will compare the counter to the inputted number...]

Go to Sunny Skies Park:n 1 r.
Pickup a passenger going to Cyclone.
Go to Cyclone:n 1 l.
Pickup a passenger going to Cyclone.
Pickup a passenger going to Magic Eight.

[...who we take now, so we can make a clone of it and compare it to the counter.]

Go to Magic Eight:s 1 l 2 r.
Switch to plan D if no one is waiting.

[Compare.]
[If the counter is waiting here, the loop is to continue.]
[If not, switch to plan D, end the loop, and start detecting whether or not the running squares total is a square itself.]

Pickup a passenger going to Addition Alley.
Go to Cyclone:n 1 l 2 r.
Switch to plan B.

[Reset everything, and loop back to the start of plan B.]

[C]

[If we are on this path, the counter is not a divisor of the inputted number, but the loop should continue anyways.]

Go to Sunny Skies Park:n.
Pickup a passenger going to Cyclone.
Pickup a passenger going to Addition Alley.
Go to Cyclone:n 1 l.
Switch to plan B.

[Reset everything, and loop back to the start of plan B.]

[D]

[We are finally out of the loop. Now it's time for the real fun.]

Go to Cyclone:n 1 l 2 r.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to Sunny Skies Park.
Go to Sunny Skies Park:n 1 r.

[We don't need the inputted number anymore, but we can't change its destination from the Cyclone.]
[So we go to the Cyclone, so we can take the two clones and bring them to Sunny Skies Park forever.]
[We could send them to Riverview Bridge, but that will take more bytes.]

Go to Rob's Rest:s 2 r 1 r.

[Pick up our running squares total from Rob's Rest, so it can go out and see the town.]

Pickup a passenger going to Cyclone.
Go to Cyclone:s 1 l 1 l 2 l.
Pickup a passenger going to Cyclone.
Pickup a passenger going to Cyclone.
Go to Zoom Zoom:n.
Go to Cyclone:w.

[We need to end up with 4 clones of the total.]
[Two of them will actually be used as the counter in this loop.]

[At the start of each loop, we have no passengers.]

[E]
Pickup a passenger going to Joyless Park.
Pickup a passenger going to Divide and Conquer.
Go to Joyless Park:n 2 r 2 r 2 l.

[We will leave one clone of the total at Joyless Park (like Sunny Side Park, but on the opposite side of town).]
[The other clone will be used in a division.]

Go to Cyclone:w 1 r 2 l 2 l.
Pickup a passenger going to Cyclone.
Pickup a passenger going to Joyless Park.
Go to Joyless Park:n 2 r 2 r 2 l.

[We will leave one clone of the counter at Joyless Park.]
[We will clone the other clone (clone-ception?).]

Go to Cyclone:w 1 r 2 l 2 l.
Pickup a passenger going to Divide and Conquer.
Pickup a passenger going to Divide and Conquer.
Go to Divide and Conquer:n 2 r 2 r 1 r.

[We will use both clones of the counter in a division.]
[Divide and Conquer can take 3 arguments, and the result here will be equivalent to total / counter^2 .]
[If the square of the counter is equal to the total, the result will be 1.]
[If the square of the counter is less than the total, the result will be greater than 1.]
[If the square of the counter is greater than the total, the result will be less than 1.]

Pickup a passenger going to Magic Eight.
1 is waiting at Starchild Numerology.
Go to Starchild Numerology:e 1 r 3 r 1 l 1 l 2 l.
Pickup a passenger going to Magic Eight.
Go to Magic Eight:w 1 r 2 r 1 r.
Switch to plan F if no one is waiting.

[We compare the result of the division against 1 to decide our next course of action.]
[If it is greater or equal, the loop should end, and the counter is equal to the floor of the square root.]
[If it is less, the loop should continue.]

Pickup a passenger going to Riverview Bridge.

[Whoops, we don't actually need this anymore.]

Go to Joyless Park:e 2 l 4 r.
Pickup a passenger going to Cyclone.

[We will clone the total later, so we can reuse it in the next loop iteration.]

Pickup a passenger going to The Underground.
Go to The Underground:w 1 l.

[Instead of taking the number 1 and subtracting it from the counter, we can do an optimization here.]
[The Underground is a destination that takes 1 passenger, and subtracts 1 from it.]
[If the result is positive, it returns the result. Otherwise, it returns no one.]
[The latter result will not happen for us, however.]

Pickup a passenger going to Cyclone.

[We will clone the counter later, so we can reuse it in the next loop iteration.]

Go to Fueler Up:s.

[Gotta remember to stop for gas!]

Go to Riverview Bridge:n 3 l.

[So long, Magic Eight result!]

Go to Cyclone:w 2 l.
Switch to plan E.

[Reset everything, and loop back to the start of plan E.]

[F]

Go to Joyless Park:e 2 l 4 r.
Pickup a passenger going to What's The Difference.
Pickup a passenger going to Cyclone.

[Once we've figured out the square root of the total, we're still not done.]

Go to Cyclone:w 1 r 2 l 2 l.
Pickup a passenger going to Multiplication Station.
Pickup a passenger going to Multiplication Station.
Go to Multiplication Station:s 1 l 2 r 4 l.

[We actually square the square root...]

Pickup a passenger going to What's The Difference.
Go to What's The Difference:n 2 l 1 r 3 l.

[...and subtract it from the total at What's The Difference (which subtracts dropped-off passengers).]

Pickup a passenger going to Knots Landing.
Go to Knots Landing:e 4 r 1 l.

[If the result is 0, the total is a perfect square, and a truthy value should be output.]
[If the result is nonzero, the total is not a perfect square, and a falsy value should be output.]
[Luckily, Knots Landing does our work for us.]
[Knots Landing inverts the boolean logic of numeric passengers (i.e. 0 becomes 1, nonzero becomes 0).]

Pickup a passenger going to The Babelfishery.
Go to The Babelfishery:w 1 l.

[Convert it to a string...]

Pickup a passenger going to Post Office.
Go to Post Office:n 1 l 1 r.

[...and output it.]

[We would exit the program by going to the Taxi Garage, but that takes bytes.]
[The boss fires us because we didn't bring the taxi back to the garage, but that gets output to STDERR, so that's OK.]

```
> 2 votes

# Answer
# Vyxal, 5 bytes

```
K²∑∆²

```

Try it Online!

```
   ∆² # Is
  ∑   # The sum of
 ²    # The squares of
K     # The factors of the input
   ∆² # A perfect square?

```
> 2 votes

# Answer
# Vyxal, 14 bytes (Test cases)

```
ɾḊT›ƛ:*;ƒ+√:ṙ=

```
> 2 votes

# Answer
# Jelly, 6 bytes

```
ÆD²SÆ²

```

**Try it online!** Or see the test-suite.

### How?

```
ÆD²SÆ² - Main Link: integer
ÆD     - divisors
  ²    - square
   S   - sum
    Æ² - is square?

```
> 1 votes

# Answer
# Husk, 6 bytes

```
£İ□ṁ□Ḋ

```

Try it online!

### Explanation

```
£İ□ṁ□Ḋ  -- example input 12
     Ḋ  -- divisors: [1,2,3,4,6,12]
   ṁ    -- map the following ..
    □   -- | square: [1,4,9,16,36,144]
        -- .. and sum: 210
£       -- is it element of (assumes sorted)
 İ□     -- | list of squares: [1,4,9,16..196,225,..

```
> 1 votes

# Answer
# Gaia, 5 bytes

```
ds¦Σụ

```

Try it online!
> 1 votes

# Answer
# Proton, 41 bytes

```
a=>sum(q*q for q:1..a+1if a%q<1)**.5%1==0

```

Try it online!

Similar approach to the Python answer.
> 1 votes

# Answer
# Mathematica, 32 bytes

```
IntegerQ@Sqrt[2~DivisorSigma~#]&

```

Pure function. Takes a number as input and returns `True` or `False` as output. Not entirely sure if there's a shorter method for checking perfect squares.
> 1 votes

# Answer
# Octave / MATLAB, 43 bytes

```
@(n)~mod(sqrt(sum(find(~mod(n,1:n)).^2)),1)

```

Try it online!
> 1 votes

# Answer
# Perl 6, 34 bytes

*-1 byte thanks to nwellnhof*

```
{grep($_%%*,1..$_)>>².sum**.5%%1}

```

Try it online!
> 1 votes

# Answer
# Scala, ~~68~~ 67 bytes

```
def j(s:Int)=Math.sqrt((1 to s).filter(s%_<1).map(a=>a*a).sum)%1==0

```

Try it online!
> 1 votes

# Answer
# Java 8, ~~75~~ 70 bytes

```
n->{int s=0,i=0;for(;++i<=n;)s+=n%i<1?i*i:0;return Math.sqrt(s)%1==0;}

```

-5 bytes thanks to *@archangel.mjj*.

Try it online.

**Explanation:**

```
n->{             // Method with integer parameter and boolean return-type
  int s=0,       //  Sum-integer, starting at 0
      i=0;       //  Divisor integer, starting at 0
  for(;++i<=n;)  //  Loop `i` in the range [1, n]
    s+=n%i<1?    //   If `n` is divisible by `i`:
        i*i      //    Increase the sum by the square of `i`
       :         //   Else:
        0;       //    Leave the sum the same by adding 0
  return Math.sqrt(s)%1==0;}
                 //  Return whether the sum `s` is a perfect square

```
> 1 votes

# Answer
# Red, 67 bytes

```
func[n][s: 0 repeat d n[if n % d = 0[s: d * d + s]](sqrt s)% 1 = 0]

```

Try it online!
> 1 votes

# Answer
## F#, 111 bytes

```
let d n=Seq.where(fun v->n%v=0){1..n}
let u n=
 let m=d n|>Seq.sumBy(fun x->x*x)
 d m|>Seq.exists(fun x->x*x=m)

```

Try it online!

So `d` gets the divisors for all numbers between 1 and `n` inclusive. In the main function `u`, the first line assigns the sum of all squared divisors to `m`. The second line gets the divisors for `m` and determines if any of them squared equals `m`.
> 1 votes

# Answer
# Perl 5, 47 bytes

```
$a+=$_*$_*!($n%$_)for 1..$n;$a=!($a**.5=~/\D/);

```

Returns 1 for true and nothing for false.

### Explanation:

```
$a+=              for 1..$n;                      sum over i=1 to n
    $_*$_                                         square each component of the sum
         *!($n%$_)                                multiply by 1 if i divides n.
                            $a=                   a equals
                                ($a**.5           whether the square root of a
                               !       =~/\D/);   does not contain a non-digit.

```
> 1 votes

# Answer
# Groovy, 47 bytes

A lambda accepting a numeric argument.

```
n->s=(1..n).sum{i->n%i?0:i*i}
!(s%Math.sqrt(s))

```

**Explanation**

`(1..n)` creates an array of the values 1 to n

`n%i` is false (as 0 is falsy) if `i` divides `n` without remainder

`n%i ? 0 : i*i` is the sum of the square of the value `i` if it divides `n` without remainder, otherwise is 0

`sum{ i-> n%i ? 0 : i*i }` sums the previous result across all `i` in the array.

`s%Math.sqrt(s)` is false (as 0 is falsy) if the sqrt of `s` divides `s` without remainder

`!(s%Math.sqrt(s))` returns from the lambda (`return` implicit on last statement) `!false` when the sqrt of `s` divides `s` without remainder

Try it online!
> 1 votes

# Answer
# Stax, ~~10~~ 9 bytes

```
▀ùj╦┬44eR

```

Run and debug it at staxlang.xyz!

### Unpacked (11 bytes) and explanation:

```
:d{J+kc|qJ=
:d             Implicit input. Make list of divisors.
  {  k         Reduce using block:
   J+            Square and add to the running total.
      c        Copy this sum of squares on the stack.
       |qJ     Take square root, rounding down. Square.
          =    Check for equality.

```
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), ~~141~~ ~~137~~ ~~135~~ ~~131~~ 61 bytes

Thanks ASCII-only.

```
a=>Math.Sqrt(Enumerable.Range(1,a).Sum(b=>a%b==0?b*b:0))%1==0

```

Explanation:

```
a => Math.Sqrt(                                                    ) % 1 == 0 //Square root, test for whole number
               Enumerable.Range(1, a).Sum(                        ) //Sum 1 through a with..
                                          b => a % b==0 ? b * b: 0 //b^2 if a modulo b = 0, else 0

```

Try it online!
> 1 votes

# Answer
# Pyth, 26 16 bytes

```
!%@s^R2*M{yPQ2 1

```

Try it online!

I'm new to Pyth (and golfing in general) so this is pretty bad. Pyth doesn't have a built-in to get divisors, so I had to do that. Up until the perfect-square check, it was pretty alright, but after that it became a bit cluttered because of the if statement. Criticism is welcome.

*-10 bytes thanks to Sok*

Explanation:

```
            Q               #get user input
       *M{yP                #get the divisors
    ^R2                     #square each divisor
   s                        #sum the list
  @          2              #get square root
 %             1            #check if sqrt is a whole number (mod 1)
!                           #invert (0 -> True, any other num -> False)

```
> 1 votes

# Answer
# Wolfram Language (Mathematica), ~~24~~ 20 bytes

```
1∣Norm@Divisors@#&

```

Try it online!

`Divisors` finds all the divisors of a number, `Norm` takes the square root of the sum of squares, and then we test if this is divisible by 1 (i.e., is an integer).
> 1 votes

# Answer
# C# (.NET Core), ~~115~~ 74 bytes

Thanks to user Misha Lavrov for teaching me how to properly do code golf! :)

```
a=>{int s=0;for(int i=0;i++<=a;)s+=a%i==0?i*i:0;return Math.Sqrt(s)%1==0;}

```

Try it online!

Ungolfed:

```
a => {                              // reads input
    int s = 0;                      // holds sum of squares
    for(int i = 0; i++ <= a;)       // index from 1 to input, inclusive
    {
        s +=                        // add to sum
            a % i == 0 ?            // check if remainder of input divided by current index is zero
                i * i : 0;          // if true, add square of current index, else add zero
    }
    return Math.Sqrt(s) % 1 == 0;   // prints "True" if square root is whole number, "False" otherwise
}

```
> 1 votes

# Answer
# Ohm v2, 5 bytes

```
V²ΣÆ²

```

Try it online! Explanation:

```
V²ΣÆ²
V      Pushes input's divisors
 ²     Squares
   Σ   Sum
    Æ² Returns whether value is a proper square.

```
> 1 votes

# Answer
# APL(NARS), 23 chars, 46 bytes

```
{0=1∣√+/×⍨(0=a∣⍵)/a←⍳⍵}

```

test:

```
   g←{0=1∣√+/×⍨(0=a∣⍵)/a←⍳⍵}
   g¨ 42 1 246 10 16
1 1 1 0 0

```
> 1 votes

# Answer
# Arturo, 39 bytes

```
$=>[=floor<=sqrt∑map factors&'x->x*x]

```

Try it!

```
$=>[              ; a function where input is assigned to &
    factors&      ; divisors of the input
    map _ 'x->x*x ; square each
    ∑             ; sum
    sqrt          ; square root
    <=            ; duplicate
    floor         ; floor
    =             ; are the equal?
]                 ; end function

```
> 1 votes

# Answer
# Ruby, 45 bytes

```
->n{(1..n).map{n%_1<1?_1*_1:0}.sum**0.5%1==0}

```

Attempt This Online!
> 1 votes

# Answer
# ARBLE, 33 bytes

```
nt(sqrt(1+sum(factors(n)|x^2))%1)

```

Try it online!
> 0 votes

---
Tags: code-golf, math, number, decision-problem
---


# Question
Title: Compute convolution quickly and accurately
# Input

An array A of integers of length 100,000. The array will contain only integers in the range 0 to 1e7.

# Output

The convolution of A with itself. As this will be of length 199999 you should time just the convolution calculation however, not the time to print out the answer.

# Example in Python

```
import numpy as np
from scipy.signal import convolve
A = np.array([0]+ [1e7]*99999)
B = convolve(A,A, method="direct")

```

If I run this code the convolution line takes about 0.74s. It is over 4s if use a list instead of a numpy array.

# Precision

If I use the numpy FFT method with:

```
convolve(A,A,method="fft")

```

it is very fast but I get the wrong answer due to precision problems.

# Task

Write code to perform convolution that gives the correct output for all inputs in the specified range. Your score will be the factor by which your code is faster than the above code on my computer.

# Computer

I will run your code on Ubuntu on a AMD Ryzen 5 3400G.

# Possible speed ups

Apart from clever coding tricks and parallelization, the following may (or may not) be useful.

# Edit

Largest value reduced to 1e7 so that only 64 bit unsigned ints are needed.

# Table of leaders per language

* Score **0.49**. Takes 1.52s in **Python** by **l4m2**
* Score **36**. Takes 0.02s in **C++** by **dingledooper**
* Score **5.3**. Takes 0.14s in **Rust** by **Bubbler**
* Score **50.3**. Takes 0.015s in **Rust** by **Bubbler** . This is running `ntt_par`.

# Answer
> 7 votes
# C++ (gcc), ~0.01s

```
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <ctime>
#include <immintrin.h>

struct C {
    double x, y;
    C() : x(0), y(0) {}
    C(double x, double y) : x(x), y(y) {}
    inline C operator+ (const C &c) const { return C(x + c.x, y + c.y); }
    inline C operator- (const C &c) const { return C(x - c.x, y - c.y); }
    inline C operator* (const C &c) const { return C(x * c.x - y * c.y, x * c.y + y * c.x); }
    inline C conj() const { return C(x, -y); }
};

constexpr double PI = acos(-1);
constexpr int SIZE = 100000, B = 32 - __builtin_clz(SIZE * 2 - 1), N = 1 << B;

alignas(32) C w[N >> 2], f0[N], f1[N];

void init_roots() {
    w[0] = C(1, 0);
    for (int len = 1; len < (N >> 2); len <<= 1) {
        C wn(cos(PI / (len << 2)), sin(PI / (len << 2)));
        for (int i = len; i < len << 1; i++)
            w[i] = w[i - len] * wn;
    }
}

__m256d avx_complex_mul(__m256d a, __m256d b) {
    __m256d ax = _mm256_unpacklo_pd(a, a);
    __m256d ay = _mm256_unpackhi_pd(a, a);
    __m256d bs = _mm256_shuffle_pd(b, b, 5);
    return _mm256_fmaddsub_pd(ax, b, _mm256_mul_pd(ay, bs));
}

void fft(C *f) {
    for (int len = N >> 2; len > 1; len >>= 2) {
        for (int i = 0, m = 0; i < N; i += len << 2, m++) {
            double w1x = w[m].x, w1y = w[m].y;
            double w2x = w1x * w1x - w1y * w1y, w2y = 2 * w1x * w1y;
            double w3x = w1x * w2x - w1y * w2y, w3y = w1x * w2y + w1y * w2x;

            __m256d w1 = _mm256_setr_pd(w1x, w1y, w1x, w1y);
            __m256d w2 = _mm256_setr_pd(w2x, w2y, w2x, w2y);
            __m256d w3 = _mm256_setr_pd(w3x, w3y, w3x, w3y);

            constexpr __m256d posneg = { 0.0, -0.0, 0.0, -0.0 };

            for (int j = i; j < i + len; j += 2) {
                __m256d c0 = _mm256_load_pd(&f[j + len * 0].x);
                __m256d c1 = avx_complex_mul(_mm256_load_pd(&f[j + len * 1].x), w1);
                __m256d c2 = avx_complex_mul(_mm256_load_pd(&f[j + len * 2].x), w2);
                __m256d c3 = avx_complex_mul(_mm256_load_pd(&f[j + len * 3].x), w3);

                __m256d a02 = _mm256_add_pd(c0, c2);
                __m256d a13 = _mm256_add_pd(c1, c3);
                __m256d s02 = _mm256_sub_pd(c0, c2);
                __m256d s13 = _mm256_xor_pd(posneg, _mm256_sub_pd(c1, c3));
                s13 = _mm256_shuffle_pd(s13, s13, 5);

                _mm256_store_pd(&f[j + len * 0].x, _mm256_add_pd(a02, a13));
                _mm256_store_pd(&f[j + len * 1].x, _mm256_sub_pd(a02, a13));
                _mm256_store_pd(&f[j + len * 2].x, _mm256_add_pd(s02, s13));
                _mm256_store_pd(&f[j + len * 3].x, _mm256_sub_pd(s02, s13));
            }
        }
    }

    for (int i = 0, m = 0; i < N; i += 4, m++) {
        C w1 = w[m], w2 = w1 * w1, w3 = w1 * w2;
        C c0 = f[i + 0], c1 = f[i + 1] * w1,
          c2 = f[i + 2] * w2, c3 = f[i + 3] * w3;
        C a02 = c0 + c2, a13 = c1 + c3,
          s02 = c0 - c2, s13 = (c1 - c3) * C(0, 1);
        f[i + 0] = a02 + a13, f[i + 1] = a02 - a13;
        f[i + 2] = s02 + s13, f[i + 3] = s02 - s13;
    }
}

void ifft(C *f) {
    for (int i = 0, m = 0; i < N; i += 4, m++) {
        C w1 = w[m], w2 = w1 * w1, w3 = w1 * w2;
        C c0 = f[i + 0], c1 = f[i + 1],
          c2 = f[i + 2], c3 = f[i + 3];
        C a01 = c0 + c1, a23 = c2 + c3,
          s01 = c0 - c1, s23 = (c2 - c3) * C(0, 1);
        f[i + 0] = a01 + a23, f[i + 1] = (s01 + s23) * w1;
        f[i + 2] = (a01 - a23) * w2, f[i + 3] = (s01 - s23) * w3;
    }

    for (int len = 4; len < N; len <<= 2) {
        for (int i = 0, m = 0; i < N; i += len << 2, m++) {
            double w1x = w[m].x, w1y = w[m].y;
            double w2x = w1x * w1x - w1y * w1y, w2y = 2 * w1x * w1y;
            double w3x = w1x * w2x - w1y * w2y, w3y = w1x * w2y + w1y * w2x;

            __m256d w1 = _mm256_setr_pd(w1x, w1y, w1x, w1y);
            __m256d w2 = _mm256_setr_pd(w2x, w2y, w2x, w2y);
            __m256d w3 = _mm256_setr_pd(w3x, w3y, w3x, w3y);

            constexpr __m256d posneg = { 0.0, -0.0, 0.0, -0.0 };

            for (int j = i; j < i + len; j += 2) {
                __m256d c0 = _mm256_load_pd(&f[j + len * 0].x);
                __m256d c1 = _mm256_load_pd(&f[j + len * 1].x);
                __m256d c2 = _mm256_load_pd(&f[j + len * 2].x);
                __m256d c3 = _mm256_load_pd(&f[j + len * 3].x);

                __m256d a01 = _mm256_add_pd(c0, c1);
                __m256d a23 = _mm256_add_pd(c2, c3);
                __m256d s01 = _mm256_sub_pd(c0, c1);
                __m256d s23 = _mm256_xor_pd(posneg, _mm256_sub_pd(c2, c3));
                s23 = _mm256_shuffle_pd(s23, s23, 5);

                _mm256_store_pd(&f[j + len * 0].x, _mm256_add_pd(a01, a23));
                _mm256_store_pd(&f[j + len * 1].x, avx_complex_mul(_mm256_add_pd(s01, s23), w1));
                _mm256_store_pd(&f[j + len * 2].x, avx_complex_mul(_mm256_sub_pd(a01, a23), w2));
                _mm256_store_pd(&f[j + len * 3].x, avx_complex_mul(_mm256_sub_pd(s01, s23), w3));
            }
        }
    }
}

void convolve(uint64_t *a) {
    init_roots();
    for (int i = 0; i < SIZE; i++)
        f0[i] = C(a[i] & 4095, a[i] >> 12);
    fft(f0);

    double t0 = 4 * f0[0].x * f0[0].y, t1 = 4 * f0[1].x * f0[1].y;
    f1[0].x = 4 * f0[0].y * f0[0].y, f1[0].y = 0;
    f1[1].x = 4 * f0[1].y * f0[1].y, f1[1].y = 0;
    f0[0].x = 4 * f0[0].x * f0[0].x, f0[0].y = t0;
    f0[1].x = 4 * f0[1].x * f0[1].x, f0[1].y = t1;

    for (int i = 2, msk = 0; i < N; i += 2) {
        msk |= i >> 1;
        int j = i ^ msk;
        C c0 = f0[i] + f0[j].conj();
        C c1 = (f0[i] - f0[j].conj()) * C(0, -1);
        C c00 = c0 * c0, c01 = c0 * c1, c11 = c1 * c1;
        f0[i] = c00.conj() + c01.conj() * C(0, 1), f0[j] = c00 + c01 * C(0, 1);
        f1[i] = c11.conj(), f1[j] = c11;
    }
    ifft(f0); ifft(f1);

    for (int i = 0; i < SIZE * 2 - 1; i++) {
        uint64_t c0 = (uint64_t) (f0[i].x / (N << 2) + 0.5);
        uint64_t c1 = (uint64_t) (f0[i].y / (N << 2) + 0.5);
        uint64_t c2 = (uint64_t) (f1[i].x / (N << 2) + 0.5);
        a[i] = c0 + (c1 << 13) + (c2 << 24);
    }
}

uint64_t A[SIZE * 2 - 1];

int main() {
    for (int i = 1; i < SIZE; i++) A[i] = 1e7;
    clock_t start = clock();
    convolve(A);
    clock_t end = clock();
    uint64_t checksum = 0;
    for (int i = 0; i < SIZE * 2 - 1; i++) checksum ^= A[i];
    printf("checksum: %llu\n", checksum);
    printf("cpu time: %.3fs\n", (double) (end - start) / CLOCKS_PER_SEC);
    return 0;
}

```

Try it online!

Run with `-O3` or `-Ofast` enabled for best performance. The `-march=native` may also be necessary to run.

Uses a standard floating-point radix-4 FFT. Each input integer is split into two 12-bit chunks to avoid precision loss. Since the input comprises of only real numbers, we can get away with doing just a single FFT by using `a&4095` as the real part and `a>>12` as the imaginary part. Upon converting back we still need two FFTs as the output space is twice as large.

**Update:**

* I realized that the bit reversal was unusually time consuming, so I got rid of it using a DIF-DIT scheme. DIF takes the input in normal order and outputs in bit-reversed order, while DIT takes a bit-reversed input and outputs in normal order. Thus, they magically cancel out :)
* I made another mistake in assuming that `llround` was relatively fast. Apparently adding `+0.5` and then truncating is nearly 10x faster than `llround`, which led to a ~30% improvement.
* Added SIMD in the FFT loop. This one didn't help that much, presumably because GCC already auto-vectorizes it.

# Answer
> 6 votes
# Python 3, 3 seconds

```
R = "".join("%028o"%x for x in A)
B = int(R,8)**2 | (1 << 599997*28)
t = oct(B)
G = [int(t[3+i*28:31+i*28],8) for i in range(199999)]

```

Try it online!

Was a golfing solution somewhere else but also mine

# Answer
> 5 votes
# Rust + num-bigint or dashu, ~0.3 seconds locally

```
use num_bigint::BigUint;
use dashu::integer::UBig;
use std::time::Instant;

fn solve_num(input: &[u64]) -> (Vec<u64>, u128) {
    let mut num = Vec::with_capacity(input.len() * 2);
    for &x in input {
        num.push(x as u32);
        num.push(0);
    }
    let big = BigUint::from_slice(&num);
    let instant = Instant::now();
    let big2 = &big * &big;
    let elapsed = instant.elapsed().as_micros();
    (big2.to_u64_digits(), elapsed)
}

fn solve_dashu(input: &[u64]) -> (Vec<u64>, u128) {
    let big = UBig::from_words(input);
    let instant = Instant::now();
    let square = big.square();
    let elapsed = instant.elapsed().as_micros();
    (square.as_words().to_vec(), elapsed)
}

fn main() {
    let input = (
        vec![10_000_000u64; 100_000],
        vec![1; 5]
    ).0;

    let (result, elapsed) = solve_num(&input);
    println!("elapsed: {}.{:06}", elapsed / 1000000, elapsed % 1000000);
    eprintln!("{:?}", result);

    let (result, elapsed) = solve_dashu(&input);
    println!("elapsed: {}.{:06}", elapsed / 1000000, elapsed % 1000000);
    eprintln!("{:?}", result);
}

```

Instructions to run:

* Create a cargo project with `cargo new cg263748`
* Add dependencies in `Cargo.toml`:
```
[dependencies]
num-bigint = "0.4"
dashu = "0.3"

```
* Replace the content of `src/main.rs` with the source above
* Run with `cargo run --release 2>/dev/null`

Both num-bigint and dashu seem to use "naive/Karatsuba/Toom-3 combo" for inputs with different sizes. For the largest sizes, the main algorithm used is Toom-3. For an input vector of size `10^5`, num-bigint takes ~0.31s and dashu takes ~0.27s.

---

I do have an NTT source code for personal use, but I highly doubt it will be competitive given that a term can go up to `10^19`, which means I have to either use 128-bit multiplication and division in the main algorithm, or convolve twice using two (or maybe three) different modulos and combine them using Chinese Remainder Theorem.

EDIT: Apparently it is possible to do a single NTT with a prime very close to 2^64, using one of the algorithms described in this paper. e.g. one could choose `p = 10485760000033554433`, where `5` is a primitive root. Unfortunately the faster ones won't work because the prime must be under 2^63 for them.

EDIT 2: I'm working on the NTT implementation on the paper. I realized I need to do elementwise `a * b % P` anyway, so I came up with a "u128 division"-less algorithm (godbolt) for a specific P = `71 * 2^57 + 1` = `10232178353385766913`. This is three times as fast as naive `(a as u128 * b as u128 % P as u128) as u64`:

```
slow mulmod             time:   [21.182 ns 21.185 ns 21.188 ns]
fast mulmod             time:   [7.0764 ns 7.1222 ns 7.1864 ns]

```

# Answer
> 4 votes
# Rust, ~0.048s locally; Rust + rayon, ~0.039s locally

The main code (sequential, independent of rayon) is as follows:

```
pub const P: u64 = 10232178353385766913;

pub fn mulmod(a: u64, b: u64) -> u64 {
    let x = a as u128 * b as u128;
    let y = x >> 57;
    let y1 = (y >> 35) as u64;
    let y2 = y as u64 & ((1u64 << 35) - 1);
    let y_div_71 = y1 * 483939977 + (y1 + y2) / 71;
    let sub = y_div_71 as u128 * P as u128;
    let (res, borrow) = x.overflowing_sub(sub);
    if borrow { (res as u64).wrapping_add(P) } else { res as u64 }
}

fn powmod(a: u64, p: u64) -> u64 {
    let mut cur = 1;
    let mut pow = a;
    let mut p = p;
    while p > 0 {
        if p % 2 > 0 {
            cur = mulmod(cur, pow);
        }
        p /= 2;
        pow = mulmod(pow, pow);
    }
    cur
}

fn ntt<const INV: bool>(input: &mut [u64], omega_table: &[u64], inv_p2: u64) {
    // length is a power of 2
    let len = input.len();
    let l = len.trailing_zeros() as usize;
    for i in 1..len {
        let j = i.reverse_bits() >> (64 - l);
        if i < j { input.swap(i, j); }
    }

    let mut root_pow = len / 2;
    for intvl_shift in 1..=l {
        let intvl = 1usize << intvl_shift;
        input.chunks_exact_mut(intvl).for_each(|chunk| {
            let mut root_idx = 0;
            let (left, right) = chunk.split_at_mut(intvl / 2);
            for (u, v) in left.into_iter().zip(right) {
                let u2 = *u;
                let v2 = mulmod(*v, omega_table[root_idx]);
                let (mut x, overflow) = u2.overflowing_sub(P - v2);
                if overflow { x = x.wrapping_add(P); }
                *u = x;
                let (mut y, overflow) = u2.overflowing_sub(v2);
                if overflow { y = y.wrapping_add(P); }
                *v = y;
                root_idx = root_idx + root_pow; // & len - 1;
            }
        });
        root_pow /= 2;
    }
    if INV {
        for x in input.into_iter() { *x = mulmod(*x, inv_p2); }
    }
}

fn ntt_precompute(len: usize) -> (Vec<u64>, Vec<u64>) {
    let l = len.trailing_zeros();

    let primitive_root = 3;
    let omega = powmod(primitive_root, P >> l);
    let mut omega_table = vec![1];
    // let mut omega_table_prime = vec![((1u128 << 64) / P as u128) as u64];
    for i in 1..len {
        // omega_table.push((omega_table[i-1] as u128 * omega as u128 % P as u128) as u64);
        omega_table.push(mulmod(omega_table[i-1], omega));
        // omega_table_prime.push((((omega_table[i] as u128) << 64) / P as u128) as u64);
    }
    let mut inv_p2 = 1;
    let mut inv_p2_table = vec![1];
    for _ in 0..l {
        if inv_p2 % 2 == 0 { inv_p2 /= 2; }
        else { inv_p2 = inv_p2 / 2 + P / 2 + 1; }
        inv_p2_table.push(inv_p2);
    }
    (omega_table, inv_p2_table)
}

pub fn solve_ntt(a: &[u64]) -> (Vec<u64>, u128) {
    let instant = Instant::now();

    let len_max = a.len().next_power_of_two() * 2;
    let (mut omega_table, inv_p2_table) = ntt_precompute(len_max);
    let inv_p2 = inv_p2_table[len_max.trailing_zeros() as usize];

    let mut a2 = a.to_vec();
    a2.resize(len_max, 0);
    ntt::<false>(&mut a2, &omega_table, inv_p2);
    for ax in a2.iter_mut() {
        *ax = mulmod(*ax, *ax);
    }
    omega_table[1..].reverse();
    ntt::<true>(&mut a2, &omega_table, inv_p2);
    a2.truncate((a.len() * 2).saturating_sub(1));

    let elapsed = instant.elapsed().as_micros();

    (a2, elapsed)
}

```

This is the version that takes ~0.048s. The code uses NTT (Number Theoretic Transform) with modulo `P = 10232178353385766913 = 71 * 2^57 + 1`. `mulmod` was the major bottleneck until I changed it from u128 multiplication/division to the specialized algorithm for this specific `P`.

I also made three variations using `rayon` to parallelize parts of code when possible, with different heuristics. These versions aren't performing well in my local (which is actually a cloud server with only 2 vCPUs) except for the first, but I believe they'll all outperform the original on better CPUs.

The entire code can be found at https://github.com/Bubbler-4/cg263748. The functions are `solve_ntt`, `solve_ntt_par`, `solve_ntt_par2`, and `solve_ntt_par3` in `lib.rs`.

Run instructions:

* Clone the repo
* `cargo run --release` to see timings and check that the outputs match
* `cargo bench` to run the benchmark using the same input (rayon-powered versions are showing very high variance on my local)

---
Tags: fastest-code
---


title: Iterated partial sums

text:
# Question
Title: Iterated partial sums
The partial sums of a list of integers \[a1, a2, a3, ..., an\] are

s1 = a1
s2 = a1 \+ a2
s3 = a1 \+ a2 \+ a3
...
sn = a1 \+ a2 \+ ... + an

We can then take the list of partial sums \[s1, s2, s3, ..., sn\] and compute its partial sums again to produce a new list, and so on.

Related: Iterated forward differences

**Input:**

* A non-empty list of integers
* A positive number of iterations,

**Output:** Print or return the list of integers that results from taking the partial sums that many times.

Fewest bytes wins. Built-ins are OK even if they outright solve the problem.

**Test cases:**

```
f([-3, 4, 7, -1, 15], 1) == [-3, 1, 8, 7, 22]
f([-3, 4, 7, -1, 15], 3) == [-3, -5, 1, 14, 49]

```

**Leaderboard:**

```
var QUESTION_ID=59192,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/61321/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
> 16 votes
# J, 5 bytes

```
+/\^:

```

Try it online on J.js.

### How it works

* `/\` is an adverb (function that takes a left argument) that cumulatively reduces by its argument.
* Thus `+/\` is the *cumulative sum* verb.
* `^:` is the *power conjunction*; `(f ^: n) y` applies `f` a total of `n` times to `y`.
* The verb-conjunction train `+/\^:` forms an adverb that repeats `+/\` as many times as specified in its (left) argument.

`x (+/\^:) y` gets parsed as `(x (+/\^:)) y`, which is equivalent to executing `(+/\^:x) y`.

*Thanks to @Zgarb for his help with the explanation.*

# Answer
> 13 votes
# Mathematica, 19 bytes

Well, if built-ins are okay...

```
Accumulate~Nest~##&

```

Defines a function with the same signature as the examples in the challenge. I'm pretty sure, thanks to the long name `Accumulate` that this will be easily beaten by the golfing languages and the APL-family, though. :)

To elaborate on LegionMammal978's comment for those who don't Mathematica:

`##` represents a *sequence* of the function's parameters (which is like a list that automatically "splats" wherever it's inserted, if you're more familiar with that term from your language's of choice). The `~` are syntactic sugar for infix function invocation, so if we call the function with parameters `list` and `n` and expand everything, we get:

```
Accumulate~Nest~##
Nest[Accumulate, ##]
Nest[Accumulate, list, n]

```

Which happens to be exactly the argument order expected by `Nest`.

# Answer
> 9 votes
# APL, ~~9~~ 8 bytes

```
{+\⍣⍺⊢⍵}

```

This defines a dyadic function that accepts the iterations and list as left and right arguments.

*Thanks to @NBZ for golfing off 1 byte!*

Try it online on TryAPL.

### How it works

* and  are the left and right arguments to the function.
* `+\` is cumulative reduce by sum.
* `⍣⍺` repeats the preceding operator  times.
* `⊢⍵` applies the identity function to .

This is a shorter way of parsing the code as `(+\⍣⍺)⍵` instead of `+\⍣(⍺⍵)`.

In conjunction, we apply `+\` a total of  times to

# Answer
> 9 votes
## Haskell, ~~26~~ 23 bytes

```
(!!).iterate(scanl1(+))

```

This defines an anonymous function, invoked as follows:

```
> let f = (!!).iterate(scanl1(+)) in f [-3,4,7,-1,15] 3
[-3,-5,1,14,49]

```

Thanks to @nimi for saving 3 bytes.

## Explanation

```
(!!).                    -- Index by second argument from
     iterate(         )  -- the infinite list obtained by iterating
             scanl1(+)   -- the partial sums function (left scan by +) to first argument

```

# Answer
> 5 votes
# Matlab, 41 bytes

```
function f(l,n);for i=1:n;l=cumsum(l);end

```

Quite straightforward. I still think it is quite annoying not having a built in way of making piecewise defined anonymous functions, or anchors in recursions.

Ungolfed:

```
function f(l,n);
for i=1:n;
    l=cumsum(l);
end

```

# Answer
> 5 votes
# K, ~~7~~ 3 bytes

```
{y+\/x}

```

Very similar to the J solution. `+\` precisely performs a partial sum, and when `/` is provided with a monadic verb and an integer left argument it iterates a specified number of times, like a "for" loop. The rest is just wrapping it up neatly to suit the order of arguments.

```
  {y+\/x}[-3 4 7 -1 15;1]
-3 1 8 7 22
  {y+\/x}[-3 4 7 -1 15;3]
-3 -5 1 14 49

```

Tested in Kona and oK.

## Edit:

If I'm allowed to reverse the arguments, as @kirbyfan64sos determined, I can dispense with the function wrapping entirely:

```
+\/

```

Invoked like:

```
+\/[3;-3 4 7 -1 15]

```

This works properly in both k2.8 and k5. It doesn't work in oK since that interpreter does not yet support curried (aka "projected") adverbs, and it doesn't appear to work properly in Kona for less clear reasons.

*edit*: As of a few days ago, the `+\/` formulation also works in oK.

# Answer
> 5 votes
# JavaScript (ES6) 38

Surprisingly small using .map recursively

```
f=(l,n,t=0)=>n?f(l.map(x=>t+=x),n-1):l

function test()
{
  var n, v, i = I.value
  v = i.match(/\-?\d+/g).map(x=>+x)
  n = v.pop()
  console.log(v,n)
  O.innerHTML = I.value + ' -> ' + f(v,n) + '\n' + O.innerHTML;
}

test()
```

```
<input id=I value='[-3, 4, 7, -1, 15], 3'><button onclick="test()">-></button>
<pre id=O></pre>
```

# Answer
> 4 votes
# R, 75 bytes

It's long but a different take...computing the desired sequence directly instead of cumulative sums:

```
function(x,n)sapply(1:length(x),function(i)sum(x[1:i]*choose(i:1+n-2,n-1)))

```

Noting that the coefficients of the terms of xi for cumsum^n(x) are diagonals of Pascal's triangle. i.e.

```
cumsum^3(x) = choose(2,2) * x1, choose(3,2) * x1 + choose(2,2) *x2, choose(4,2) * x1 + choose(3,2) * x2 + choose(2,2) * x3, ....

```

edit: to make a function

# Answer
> 4 votes
# Pyth, 9 bytes

```
usM._GvwQ

```

Try it online: Demonstration or Test Suite

### Explanation

```
usM._GvwQ  implicit: Q = input list
      vw   input number
u       Q  repeat the following instruction ^ times to G = Q
   ._G        sequence of prefixes of G
 sM           sum them up

```

# Answer
> 4 votes
## Python, 113 93 89 76 bytes

```
def f(l,n):
 for i in[0]*n:l=[sum(l[:j+1])for j in range(len(l))];
 print(l)

```

It works for both of the test cases. Thanks to Status, Morgan Thrapp, and Ruth Franklin for helping me golf the program down to 93, 89, and 76 bytes respectively.

# Answer
> 4 votes
# Julia, 29 bytes

```
f(x,y)=y>0?f(cumsum(x),y-1):x

```

This really doesn't need much explanation. It's a recursive function, if `y==0` then just output x. Otherwise decrement y, perform a cumsum, and recurse. Probably not the most golfed possible Julia solution, I'm still working on it.

# Answer
> 4 votes
# Gol\>\<\> 0.3.10, 22 bytes

```
SI
C>rFlMF:}+
NRl<C}<;

```

The first integer is taken to be the iteration number and the rest make up the list. The final list is outputted newline-separated.

The language is still quite young and unstable, but since I'm pretty set on these operators I thought it'd be okay.

### Explanation

```
SI            Read integer, moving down on EOF (first line runs as loop)
r             Reverse stack, putting iteration number on top

[outer loop]
F             Do #(iterations) times

[inner loop]
lMF           Do #(length of stack - 1) times
:             Duplicate top of stack
}             Rotate stack rightward (top goes to bottom)
+             Add the top two elements of the stack
C             Continue inner loop, moving down from F when loop is over

}             Rotate once more
C             Continue outer loop, moving down from F when loop is over

lRN           Print stack as (num + newline)
;             Halt

```

To see why this works, let's try a small example `[5 2 1]`:

```
[5 2 1] -- : --> [5 2 1 1] -- } -->  [1 5 2 1]  -- + --> [1 5 3]
[1 5 3] -- : --> [1 5 3 3] -- } -->  [3 1 5 3]  -- + --> [3 1 8]

-- } --> [8 3 1]

```

# Answer
> 4 votes
# Labyrinth, 73 bytes

```
;?
,"
;
#
#;}=
;  #
"#;(
_  ;={()"
#;; ( { "
  ; { !\(@
+=( =
" " "
":{:"

```

It's been a while since I answered something in Labyrinth, and this seemed doable. :)

Input format is a flat list with the number of iterations first (and then the list to apply the partial sums to). Delimiters don't matter all, as long as there is no character after the last integer, so you can use something readable like:

```
3 | -3, 4, 7, -1, 15

```

Output is newline-separated:

```
-3
-5
1
14
49

```

# Answer
> 4 votes
# Python 2, 67

This uses the same summation as Anthony Roitman, and the same recursion as Morgan Thrapp.

```
f=lambda l,n:f([sum(l[:i+1])for i in range(len(l))],n-1)if n else l

```

I developed this solution before I saw theirs, and then it just seemed easier to post it as an answer rather than a comment to either or both of them.

# Answer
> 4 votes
# , 32 bytes

```
function(l,i)diffinv(l,,i)[0:-i]

```

Try it online!

`diffinv` is the `inv`erse of `diff`, with optional parameters `lag`, `differences`, and `xi`; `lag` defaults to `1` so we skip it and we compute the the inverse of the \\$n^\text{th}\\$ difference; `xi` defaults to `0`, so it prepends `i` instances of `0` to the inverse difference list, which we discard by negative indexing.

# Answer
> 3 votes
## Python, 52 bytes

```
f=lambda l,n:n*l and f(f(l[:-1],1)+[sum(l)],n-1)or l

```

A recursive function that recurses both on the list `l` and the number of iterations `n`. Let's break it down.

First, let's consider a recursive function `g` that iterated the partial sum just once.

```
g=lambda l:l and g(l[:-1])+[sum(l)]

```

For an empty list `l`, this returns `l` itself, the empty list. Otherwise, the last entry of the partial sums of `l` is the overall sum of `l`, which is appended to the recursive result for all but the last element of `l`.

Now, let's look at a function `f` that applies `g` for `n` iterations.

```
f=lambda l,n:n and f(g(l),n-1)or l

```

When `n` is `0`, this returns the list `l` unchanged, and otherwise, applies `g` once, then calls `f` recursively with one fewer iteration remaining.

Now, let's look again at the actual code, which combines the two recursions into a single function. The idea is to treat `g(l)` as the special case `f(l,1)`.

```
f=lambda l,n:n*l and f(f(l[:-1],1)+[sum(l)],n-1)or l

```

We took `f(g(l),n-1)` from the previous definition, expanded `g(l)` into `g(l[:-1])+[sum(l)]`, and then replaced `g(_)` with `f(_,1)` to confined the recursive calls to `f`.

For the base case, we want to return `l` whenever `n==0` or `l==[]`. We combine these by noting that either one makes `n*l` be the empty list, which is Falsy. So, we recurse whenever `n*l` is non-empty, and return `l` otherwise.

Even though there are two recursive calls to `f`, this does not cause an exponential blow-up the recursive definition of the Fibonacci numbers, but remains quadratic.

# Answer
> 3 votes
# C++ (61 + 17 = 78 bytes)

```
#include<numeric>
void f(int*a,int*e,int n){for(;n--;)std::partial_sum(a,e,a);}

```

Test case:

```
#include <iostream>
#include <iterator>

int main() {
    int a[] { -3, 4, 7, -1, 15 };
    f(a, std::end(a), 3);
    for (auto i : a)
        std::cout << i << " ";
}

```

This takes a slight liberty with the specification: it uses a C-style array, passing pointers to the beginning and end of the array. Internally, as you can see, it's only an *extremely* thin wrapper around the `std::partial_sum` in the standard library. Rather than actually return the resulting value, it just modifies the array that's passed in.

If we don't mind pushing definitions of things to the limit (and, arguably, a bit beyond) we can define a "function" in a lambda expression:

```
#include<numeric>
#include <iostream>
#include <iterator>

int main() {
    int a[] { -3, 4, 7, -1, 15 };
    int *e = std::end(a);
    int n=3;

    auto f=[&]{for(;n--;)std::partial_sum(a,e,a);};

    f();
    for (auto i : a)
        std::cout << i << " ";
}

```

This reduces the definition of the function(-like object) to this piece:

```
[&]{for(;n--;)std::partial_sum(a,e,a);};

```

...for 40 bytes (+17 for the `#include`).

# Answer
> 3 votes
# Jelly, 3 bytes

```
SƤ¡

```

Try it online!

This is my (Mr Xcoder's) method.

# Jelly, 3 bytes

```
+\¡

```

Try it online!

This is caird coinheringaahing's solution.

# Jelly, 2 bytes

```
Ä¡

```

Try it online!

This is a newer solution.

### Method #1

```
SƤ¡  - Full program, dyadic.

  ¡  - Apply repeatedly, N times.
 Ƥ   - Map the preceding link over the prefixes of the list.
S    - Sum.
     - Output implicitly

```

### Method #2

```
+\¡  - Full program, dyadic.

  ¡  - Apply repeatedly, N times.
 \   - Cumulative reduce by:
+    - Addition.

```

### Method #3

```
Ä¡  - Full program, dyadic.

 ¡  - Apply repeatedly, N times.
Ä   - Cumulative sums.

```

# Answer
> 2 votes
## Haskell, ~~52~~ 47 bytes

First ever code golf 'attempt', and I'm very much a Haskell beginner, so comments are gladly welcomed! It was not clear in the question as to any necessary format of the function call, or whether it was taken by an argument to the program, so I used the exclamation mark as the function identifier to save a couple of spaces.

```
0!a=a
i!a=(i-1)![sum$take j a|j<-[1..length a]]

```

Usage (GHCi):

```
$ ghci partialsums.hs
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( partialsums.hs, interpreted )
Ok, modules loaded: Main.
*Main> 1![-3, 4 ,7 ,-1 ,15]
[-3,1,8,7,22]
*Main> 3![-3, 4 ,7 ,-1 ,15]
[-3,-5,1,14,49]

```

# Answer
> 2 votes
# CJam, 13 bytes

```
q~{{1$+}*]}*p

```

Test it here.

# Answer
> 2 votes
# C++14, ~~102~~ ~~103~~ 94 + 17 (include) = 111 bytes

```
#include<vector>
auto f(std::vector<int>a,int n){for(;n--;)for(int i=0;i<a.size()-1;++i)a[i+1]+=a[i];return a;}

```

Ungolfed, with test case

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

auto f(std::vector<int> a, int n)
{
    for (; n--;)
        for (int i = 0; i < a.size() - 1; ++i)
            a[i + 1] += a[i];
    return a;
}

int main()
{
    auto t = f({-3, 4, 7, -1, 15}, 3);
    for (int i : t)
        std::cout << i << " ";
}

```

~~Relies on order of evaluation. Not sure if it is UB or not, but works~~ It's compiler dependent, so I changed it.

# Answer
> 2 votes
## R, 41 bytes

```
function(x,n){for(i in 1:n)x=cumsum(x);x}

```

# Answer
> 2 votes
# C#, 52 + 85 = ~~148~~ 137 bytes

```
using E=System.Collections.Generic.IEnumerable<int>;

```

and

```
E I(E s,int i){int t=0;return i<1?s:I(System.Linq.Enumerable.Select(s,v=>t+=v),i-1);}

```

It uses unorthodox practices (`v=>t+=v`), but this is PPCG. Also note the stack depth constraint.

# Answer
> 2 votes
# Python 3, 73

Could probably be golfed down a bit further.

```
def f(n,i):
 p=0;c=[]
 for m in n:p+=m;c+=[p]
 f(c,i-1)if i else print(n)

```

This version uses numpy, which feels a little like cheating, but here it is:

# Python 3 (with numpy), 72

```
from numpy import*
def f(n,i):
 if i:c=cumsum(n);f(c,i-1)
 else:print(n)

```

# Answer
> 1 votes
# Octave, 24 bytes

```
@(l,n)l*triu(0*l'*l+1)^n

```

# Answer
> 1 votes
## Burlesque, 10 bytes

```
{q++pa}jE!

```

it's not very efficient in general but it does the trick.

```
blsq ) {-3 4 7 -1 15} 1 {q++pa}jE!
{-3 1 8 7 22}
blsq ) {-3 4 7 -1 15} 3 {q++pa}jE!
{-3 -5 1 14 49}

```

# Answer
> 1 votes
# C++14, 67 bytes

As unnamed lambda modifying its input, requiring `c` as a random-access-container like `vector<int>`.

```
[](auto&c,int n){while(n--)for(int i=0;i++<c.size();c[i]+=c[i-1]);}

```

# Answer
> 1 votes
# 05AB1E, 4 bytes

```
F.pO

```

## Explanation

```
F    # Implicitly take first input and loop n times.
 .p  # Generate prefixes of input.
   O # Sum all prefixes (implicitly vectorized).

```

Try it online!

# Answer
> 1 votes
# Husk, ~~4~~ 3 bytes

Saved 1 byte thanks to Dominic Van Essen

```
!¡∫

```

Try it online!

```
!¡∫
 ¡   Repeatedly apply the following function to the first argument, making an infinite list
  ∫  Cumulative sum (one cycle)
!    Index into this list with the second argument

```

# Answer
> 1 votes
# Lua (67 bytes)

```
function x(t,n)return load("return "..table.concat(t,"+",1,n))()end

```

Explanation:

`table.concat(t,"+",1,n)` gives the string formed by concatenation of elements of `t` from 1 to n using `+` as connector, i.e. `t[1]+...+t[n]`.

`load(<string>)()`, as its name suggests, loads a string to be executed as a function. In this case, a function with zero arguments given by `table.concat`.

# Answer
> 1 votes
# Vyxal, 2 bytes

Try it Online!

# Answer
> 1 votes
# Factor, 21 bytes

```
[ [ cum-sum ] times ]

```

Try it online!

# Answer
> 1 votes
# Ruby, ~~52~~ 38 bytes

-14 bytes thanks to south

```
F=->a,n{x=0;n<1?a:F[a.map{x+=_1},n-1]}

```

Attempt This Online!

# Answer
> 1 votes
# Raku, 27 bytes

```
{(@^l,{[\+] @$_}...*)[$^n]}

```

Try it online!

`[\+] @array` is how to get a list of partial sums in Raku. Here we construct an infinite sequence of sequences of partial sums and then select the one at the desired index.

# Answer
> 1 votes
# Japt `-h`, 5 bytes

```
ÆV=å+

```

Try it

```
ÆV=å+     :Implicit input of integer U & array V
Æ         :Map the range [0,U)
 V=       :  Reassign to V
   å+     :  Cumulatively reduce V by addition
          :Implicit output of last element

```

# Answer
> 1 votes
# Go, 120 bytes

```
func f(s[]int,n int)(o[]int){if n<1{return s}
o=[]int{s[0]}
for i:=range s[1:]{o=append(o,s[i+1]+o[i])}
return f(o,n-1)}

```

Attempt This Online!

# Answer
> 1 votes
# Thunno 2, 2 bytes

```
{ṡ

```

Try it online!

#### Explanation

```
{ṡ  # Implicit input
{   # Input number of times:
 ṡ  #  Cumulative sums
    # Implicit output

```

# Answer
> 0 votes
**Axiom ~~213~~ 47 bytes**

```
m(a,b)==(for i in 1..b repeat a:=scan(+,a,0);a)

```

ungolf and some example

```
 (3) -> [m([-3,4,7,-1,15],1), m([-3,4,7,-1,15],3)]
    Compiling function l with type List Integer -> List Integer
    Compiling function m with type (List Integer,Integer) -> List
       Integer

    (3)  [[- 3,1,8,7,22],[- 3,- 5,1,14,49]]
                                                       Type: List List Integer

```

# Answer
> 0 votes
# PARI/GP, 31 bytes

```
f(a,n)=Vec(Ser(a)/(1-x)^n+.5)\1
```

Attempt This Online!

Converts the list to a power series, divides it by \\$(1-x)^n\\$, and then converts it back to a list.

PARI/GP would drop the leading zeros when converting a power series into a list. So I need to do `Vec(...+.5)\1`.

---

# PARI/GP, 31 bytes

```
f(a,n)=a*matrix(#a,,i,j,i<=j)^n
```

Attempt This Online!

Multiples the \\$n\\$-th power of the upper triangular matrix of ones. A port of my octave answer.

# Answer
> 0 votes
# Nim, 64 bytes

```
import math
proc s[I](x:var seq[I],n:I)=
 for _ in 1..n:x.cumsum

```

Attempt This Online!

Outputs by mutating the array in place.

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


# Question
Title: Adding up the digits and the digits reversed
Given a number \> 0, output the sum with all digits (1 .. n) concatenated and reversed and add them up. For example, with n = 6:

The numbers 1 to 6 concatenated:

```
123456

```

Reversed:

```
654321

```

Adding them up together will result in: 777777. Another example is n = 11:

```
1 2 3 4 5 6 7 8 9 10 11 > 1234567891011

```

and

```
11 10 9 8 7 6 5 4 3 2 1 > 1110987654321

```

Adding them up together will result in `2345555545332`. This is also known as A078262.

Shortest code wins!

# Answer
# 05AB1E, 7 bytes

```
LDRJsJ+

```

Try it online.

## Explanation

```
LDRJsJ+

L        range from 1 .. input
 D       duplicate
  R      reverse
   JsJ   convert both arrays to strings
      +  add (coerces both strings to ints)

```
> 9 votes

# Answer
# Jelly, 9 bytes

```
R,U$DF€ḌS

```
> 7 votes

# Answer
## CJam, ~~15~~ 14 bytes

Thanks to Martin for shaving a byte!

```
ri,:)_W%si\si+

```

Try it online!
> 5 votes

# Answer
## Pyth, ~~12~~ 10 bytes

```
ssMjLk_BSQ

```

Thanks to @FryAmTheEggman for 2 bytes!

`Q` is the input, `S` turns it into `[1, 2, ..., input()]`, `_B` bifurcates it over `_` (reverse) to create `[rng, rev(rng)]`, `jLk` maps it over `join` by `k` (which is the "empty string" variable), `sM` maps `int` over *this* resulting array, and `s` finally calculates the sum.
> 4 votes

# Answer
# Python 3, 74

Saved 6 bytes thanks to DSM.

Nothing too exciting, join the ranges and then convert to ints and add them.

```
lambda x:sum(int(''.join(list(map(str,range(1,x+1)))[::i]))for i in(1,-1))

```
> 4 votes

# Answer
# JavaScript (ES6), ~~70~~ ~~67~~ 64 bytes

```
a=>(z=[...Array(a)].map((b,c)=>c+1)).join``- -z.reverse().join``

```

Fixed to meet requirement, as old code was made under misunderstanding of the input.
> 4 votes

# Answer
# Retina, 71

Because its blatantly the wrong tool for the job.

```
.+
$*a:$&$*
+`^(a+)a\b(.*)\b1(1+)$
$1 $& $3
 ?(\w)+ ?
$#1
\d+:?
$&$*c
c

```

Try it online.

Works for inputs up to 6, but the online interpreter times out after that.
> 3 votes

# Answer
## JavaScript (ES6), ~~67~~ 66 bytes

```
n=>(a=[...Array(n+1).keys()].slice(1)).join``- -a.reverse().join``

```

Yes, that's a space. Ugh. At least @Downgoat helped me save a byte.
> 3 votes

# Answer
# Jolf, 9 bytes

Try it here! Replace  with `\x10`.

```
+P►γzjP_γ
    zj    range 1...j
   γ      γ = ^
  ►        ^ .join("")
 P         as a number
+     P_γ  and γ reversed

```

I *may* be able to golf it by moving around the type casting.
> 3 votes

# Answer
# Vyxal `s`, 5 bytes

```
ɾḂWvṅ

```

Try it Online!

```
ɾ         range: [1 .. x]
 Ḃ        pop x, push x, reversed(x) [bifurcate]
  W       wrap the stack
   v      for each
    ṅ     join on ""

s (flag)  sum

```

-2 bytes thanks to Razetime
> 3 votes

# Answer
## Seriously, 12 bytes

```
,R;Rεj≈@εj≈+

```

Try it online!

Explanation:

```
,R;Rεj≈@εj≈+
,R;           push two copies of range(1, input()+1)
   R          reverse one copy
    εj≈@εj≈   concatenate both and cast both to ints
           +  add

```
> 2 votes

# Answer
## PowerShell, 35 bytes

```
param($a)+-join(1..$a)+-join($a..1)

```

Converts the input to ranges with `..`, then `-join`s them together, and adds 'em up.

Will work for input numbers up to `138`, while `139` will give `Infinity`, and `140` and above will barf out an awesomely verbose casting error:

```
Cannot convert value "12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413
5136137138139140" to type "System.Int32". Error: "Value was either too large or too small for an Int32."

```
> 2 votes

# Answer
# JavaScript (ES6), 99

This adds digit by digit, so it can handle numbers well above the 53 bits of precision of javascript

```
n=>eval("for(a=b=c=r='';n;a+=n--)b=n+b;for(i=a.length;i--;r=c%10+r)c=(c>9)-(-a[i]-b[i]);c>9?1+r:r")

```

**Test**

```
f=n=>eval("for(a=b=c=r='';n;a+=n--)b=n+b;for(i=a.length;i--;r=c%10+r)c=(c>9)-(-a[i]-b[i]);c>9?1+r:r")

// Less golfed
U=n=>{
  for(a=b=c=r=''; n; --n)
      b=n+b, a+=n;
  for(i=a.length; i--; r = c%10+r)
      c=(c>9)-(-a[i]-b[i]);
  return c>9? 1+r : r;
}

function test() {
  var n=+I.value
  R.textContent=f(n)
}

test()
```

```
N: <input id=I value=11 oninput="test()"> -> <span id=R></span>
```
> 2 votes

# Answer
# MATL, 13 bytes

```
:tP2:"wVXvU]+

```

*EDIT (May 20, 2016) The code in the link uses `Xz` instead of `Xv`, owing to recent changes in the language.*

**Try it online!**

```
:                % range [1,2,...,n], where n is input
 tP              % duplicate and flip
   2:"     ]     % do this twice
      w          % swap
       V         % convert array of numbers to string with numbers and spaces
        Xv       % remove spaces
          U      % convert to number
            +    % add the two numbers

```
> 2 votes

# Answer
# Pyth - 8 bytes

```
siRT_BSQ

```

Try it online here.
> 2 votes

# Answer
# Brachylog, 24 bytes

```
:1fLrcC,Lc+C=.,{,.:1re?}

```
> 2 votes

# Answer
# 05AB1E, 5 bytes

```
LJDR+

```

Explanation:

```
L     # Pushes an array containing 1 .. [implicit] input
 J    # Join the array to a string (eg. [1, 2, 3] -> 123)
  D   # Duplicate the array
   R  # Reverse the duplicate
    + # Add them together

```

Try it online!
> 2 votes

# Answer
# R, ~~34~~ ~~60~~ 64 bytes

```
f=pryr::f;g=f(as.numeric(paste(x,collapse='')));f(g(1:n)+g(n:1))

```

Assumes `pryr` package is installed. this gives `f` as a shorthand for creating functions.

Edit added 26 bytes but returns a function that works, not something entirely wrong.

Edit added another 4 bytes to handle cases above n=10 where strtoi (previously used) was returning `NA`
> 1 votes

# Answer
# Bash + coreutils, 39

```
eval echo {1..$1} + {$1..1}|tr -d \ |bc

```

Or:

```
bc<<<`eval printf %s {1..$1} + {$1..1}`

```

Ideone.
> 1 votes

# Answer
# Perl 6, 25 bytes

```
{([~] @_=1..$^n)+[R~] @_}

```

```
{
  (
    [~]           # reduce with the string concatenation infix op:
    @_ = 1 .. $^n # the range 1 to input ( also stored in @_ )
  )
  +               # add that to
  [R~] @_         # @_ reduced in reverse
}

```

### Usage:

```
for 6, 11, 12 -> $n {
  say {([~] @_=1..$^n)+[R~] @_}( $n )
}

```

```
777777
2345555545332
244567776755433

```
> 1 votes

# Answer
# Dyalog APL, 17 bytes

```
+/⍎¨∊¨⍕¨¨x(⌽x←⍳⎕)

```

prompt for input
' enumerate until input
`x←` store list in x
reverse x
`x(``)` prepend reversed list with original list
`⍕¨¨` convert each number of each list into character string
`∊¨` make each list of character strings into single character strings
`⍎¨` convert each character string into a number
`+/` sum the two numbers.
> 1 votes

# Answer
## Lua, 53 Bytes

This program takes `n` as a command-line argument.

```
s=""r=s for i=1,arg[1]do r,s=i..r,s..i end print(s+r)

```

I assumed that outputing a number with a decimal part of 0 was okay (in the form `777777.0` because this is the default way to output a number in lua (there's no distinction between integer and float)
> 1 votes

# Answer
# Lua, 57

```
a=''b=''for i=1,...do a=a..i b=b.. ...-i+1 end return a+b

```
> 1 votes

# Answer
# Perl 5, 37 bytes

25 bytes, plus 1 for `-p` and 11 for `-MList::Gen`

```
$_=<[.]1..$_>+<[R.]1..$_>

```

---

Previous solution, 40 bytes: 39, plus one for `-p`

```
@a=reverse@_=1..$_;$"=$\;$_="@a"+"@_"

```
> 1 votes

# Answer
# Perl, 36 bytes

Includes +1 for `-p`

Run with on STDIN

```
perl -p reverse.pl <<< 6

```

`reverse.pl`

```
$_=eval join"",map{abs||"+"}-$_..$_

```
> 1 votes

# Answer
## Haskell, ~~57~~ ~~56~~ 48 bytes

This could probably be golfed a bit more, but here it goes:

```
f x=read y+(read.reverse$y)where y=[1..x]>>=show

```

Edit: shaved off a space before the where.
> 1 votes

# Answer
# Factor, 59 bytes

```
[ [1,b] dup reverse [ [ present ] map concat dec> ] bi@ + ]

```

Try it online!

* `[1,b]` Create a range from 1 to the input, inclusive.
* `dup reverse` Make a copy and reverse it.
* `[ [ present ] map concat dec> ] bi@` Convert them both to numbers of concatenated numbers.
* `+` Add.
> 1 votes

# Answer
# Python 3, 79 bytes

```
a=''.join([str(i+1) for i in range(int(input()))])
print(int(a)+(int(a[::-1])))

```

Try it online!
> 1 votes

# Answer
# Thunno 2 `s`, 4 bytes

```
RJNḲ

```

Try it online!

#### Explanation

```
RJNḲ  # Implicit input
R     # Push [1..input]
 J    # Join into a string
  N   # Convert to integer
   Ḳ  # Duplicate and reverse
      # Sum the stack
      # Implicit output

```
> 1 votes

# Answer
# Mathematica, 64 bytes

```
Plus@@FromDigits/@#&[""<>ToString/@#&/@{#,Reverse@#}&[Range@#]]&

```
> 0 votes

# Answer
# Retina, 80 bytes (ISO 8859-1 encoding)

```
'+
$0¶$0
+`^(('+)')
$2 $1
+`('('+))$
$1 $2
(')+( |$)?
$#1
(\d+)¶(\d+)
$1$*'$2$*'

```

IO is in unary with `'` as the counting character. In theory supports any integer you throw at it, in practice...online interpreter refuses to process anything larger than 6 (unary `''''''`).

Try it online!
Try it online! (decimal IO - 91 bytes)
> 0 votes

# Answer
# , 12 chars / 15 bytes

```
⨭⟮⩤⁽1ï⟯⨝,Ⅰᴚ⨝

```

`Try it here (Firefox only).`

Meh.

# Explanation

Takes a range `[1,input]`, joins it; takes that same range, reverses it, then joins it; the sum of both ranges is the result.
> 0 votes

# Answer
# Ruby, 40 characters

```
->n{eval (l=[*1..n])*''+?++l.reverse*''}

```

Sample run:

```
irb(main):001:0> ->n{eval (l=[*1..n])*''+?++l.reverse*''}[11]
=> 2345555545332

irb(main):002:0> ->n{eval (l=[*1..n])*''+?++l.reverse*''}[6]
=> 777777

```
> 0 votes

# Answer
# C#, 126 bytes

```
using System.Linq;a=>{var b=Enumerable.Range(1,a);return long.Parse(string.Concat(b))+long.Parse(string.Concat(b.Reverse()));}

```

Could possibly be golfed further. Not really sure.
> 0 votes

# Answer
# Groovy, ~~42~~ 39 characters

```
{[1..it,it..1]*.join()*.toLong().sum()}

```

Sample run:

```
groovy:000> ({[1..it,it..1]*.join()*.toLong().sum()})(11)
===> 2345555545332

groovy:000> ({[1..it,it..1]*.join()*.toLong().sum()})(6)
===> 777777

```
> 0 votes

# Answer
# Groovy, 112 characters

```
def r(n){if(n==1){return n;};return n+''+r(n-1)};n=6;s=r(args[0].toLong());print s.toLong()+s.reverse().toLong()

```

run with:

```
groovy filename.groovy *input*

```
> 0 votes

# Answer
# Perl 6, 25 bytes

Either one works

```
{([~] 1..$^n)+[R~] 1..$n}
{([~] 1..$^n)+[~] $n...1}

```
> 0 votes

# Answer
## QBIC, 24 bytes, nc

```
:[a|B=B+!b$]_FB|?!A!+!B!

```

Explanation

```
:       Read command line argument as 'a'
        Generate the sequence 1 ... a
[a|     For b = 1 to a step 1
B=B+!b$ Add b cast to string to the end of B$ (starts out empty)
]       Ends the FOR loop
_FB|    Reverse (Flip) B$ and assign the result to A$
?       Show on screen
!A!+!B! A$ cast to num + B$ cast to num

```

Non-competing, the `_F` was implemented way after this challenge was posted.
> 0 votes

# Answer
# Pushy, 10 bytes

```
RV@KjOjv+#

```

**Try it online!**

```
RV    \ Push the range to both stacks.
@Kj   \ Reverse and join the first stack
Oj    \ Join the second stack
v+    \ Sum the two resulting integers
#     \ Print result

```
> 0 votes

# Answer
# Arturo, 31 bytes

```
$->n[+do join@n..1do join@1..n]

```

Try it!

```
$->n[          ; a function taking an argument n
    1..n       ; the range [1..n]
    @          ; reify to block of integers
    join       ; convert [1 2 3] to "123", for instance
    do         ; eval -- convert numeric string to integer
    n..1       ; the range [n..1]
    @          ; reify to block of integers
    join       ; convert [1 2 3] to "123", for instance
    do         ; eval -- convert numeric string to integer
    +          ; add
]              ; end function

```
> 0 votes

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


# Question
Title: Compare array of decimal sum of Integers and exact fractional part
Develop a program which takes two arrays of decimal numbers, and compare the sum of whole numbers only and the decimal part. If the sums of the whole numbers are the same, and the decimal parts of Array a are a subset of the decimal parts of Array b, return True. Otherwise, return False.

Example-1 :-

Array a ={2.5,3.0,1.3}

Array b = {5.0,1.0,0.5,0.3}

Sum of whole numbers: Array a = 2+3+1 = 6 and Array b = 5+1 =6 --Matched

Individual fraction part: Array a = 2.5 = 0.5 and Array b = 0.5--Matched

Individual fraction part: Array a = 1.3 = 0.3 and Array b = 0.3--Matched

All the above are matched, so it returns true.

Example-2 :-

Array a ={1.7,2.3}

Array b = {1.2,0.5,2.3}

Sum of the whole numbers: Array a = 2+1 = 3 and Array b = 2+1 =3 --Matched

Individual fraction part: Array a = 1.7 = 0.7 and Array b = 0.2 or .5 or .3 --No Exact match

Individual fraction part: Array a = 2.3 = 0.3 and Array b = 2.3 = 0.3 -Matched
One of the conditions is not matched, so it returns false.

# Answer
# JavaScript, 63 bytes

```
(a,b)=>a.reduce((s,n)=>s+~~(n),0)===b.reduce((s,n)=>s+~~(n),0);

```

## Test it

```
const x=(a,b)=>a.reduce((s,n)=>s+~~(n),0)===b.reduce((s,n)=>s+~~(n),0);

const A = [2.5, 3.0, 1.3];
const B = [5.0, 1.0, 0.5, 0.3];

console.log(x(A,B)); // true
```
> 1 votes

# Answer
# Mathematica ~~88~~ 81

This should be easy to beat. I was surprised that `Rationalize` was needed.

```
r=Rationalize;f=Floor;
(Tr[f@#]==Tr[f@#2] && Complement[r@Mod[#2,1],r@Mod[#, 1]]=={})&

```

---

```
(Tr[f@#]==Tr[f@#2] && Complement[r@Mod[#2,1],r@Mod[#, 1]]=={})&
@@ {{2.5, 3.0, 1.3}, {5.0, 1.0,0.5, 0.3}}

```

> True

---

```
(Tr[f@#]==Tr[f@#2] && Complement[r@Mod[#2,1],r@Mod[#, 1]]=={})& @@
{{1.7, 2.3}, {1.2, 0.5, 2.3}}

```

> False
> 0 votes

# Answer
# Python, 45 bytes

```
x=lambda a,b:sum(map(int,a))==sum(map(int,b))

```

Try it online!
> 0 votes

---
Tags: code-golf, math, functional-programming
---


title: Convert to UTF-∞

text:
# Question
Title: Convert to UTF-∞
It's 22022 and the Unicode consortium is having a problem. After the writing system of the ⮧⣝Ⅲⴄ⟢⧩⋓⣠ civilization was assigned the last Unicode block, the consortium members have been scrambling to find a new encoding to replace UTF-8. Finally UTF-∞, a proposal by Bob Rike, was adopted. UTF-∞ is backwards compatible with UTF-8. If you know how UTF-8 works, then TLDR; UTF-∞ is the natural extension of UTF-8.

UTF-∞, like UTF-8, encodes an integer to some sequence of bytes like so (each byte shown as 8 bits)

`xxxxxxxx 10xxxxxx 10xxxxxx 10xxxxxx ...`

If the sequence of bytes has length \\$n\\$, then the first \\$n\\$ `x`:s (from left to right), are set to `1` and the \\$n+1\\$:th `x` is set to 0. The rest of the `x`:s encode a big-endian binary representation of the integer.

There is an exception. If the length of the sequence is `1` (meaning the input number is less than 128), then the encoding looks as follows:

`0xxxxxxx`

Where the `x`:s contain the binary representation of the integer.

Also, in order for an encoding to be valid, the minimum amount of bytes has to be used (no overlong encodings).

Your task is to take in a non-negative integer and output the UTF-∞ representation of the integer. You can output a list/string of bytes or a list of numbers between 0 and 255 inclusive. This is so shortest code wins.

# Example

Let's take the input 8364 (the euro symbol "€") as an example. We somehow know that we need 3 bytes, so \\$n=3\\$. Let's take

`xxxxxxxx 10xxxxxx 10xxxxxx 10xxxxxx ...`

And take the first 3 bytes:

`xxxxxxxx 10xxxxxx 10xxxxxx`

Next, the first \\$n\\$ "x"s are set to 1:

`111xxxxx 10xxxxxx 10xxxxxx`

And then the leftmost "x" is set to 0. (index \\$n+1\\$ before any "x"s were replaced)

`1110xxxx 10xxxxxx 10xxxxxx`

Finally, we fill the binary expansion of 8364 (which is 10 0000 1010 1100) into the remaining "x"s

`11100010 10000010 10101100`

And convert to bytes:

`[226, 130, 172]`

Now you might wonder how we know what value of \\$n\\$ to use? One option is trial and error. Start from \\$n=1\\$ and increment \\$n\\$ until we find an \\$n\\$ where the binary expansion of our input fits.

If we had the input 70368744177663 (\\$n=9\\$) we would start like so:

`xxxxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx`

and then

`11111111 1010xxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx`

and then fill the binary expansion of 70368744177663

# Test cases

```
0 -> [0]
69 -> [69]
127 -> [127]
128 -> [194, 128]
1546 -> [216, 138]
2047 -> [223, 191]
2048 -> [224, 160, 128]
34195 -> [232, 150, 147]
65535 -> [239, 191, 191]
65536 -> [240, 144, 128, 128]
798319 -> [243, 130, 185, 175]
2097151 -> [247, 191, 191, 191]
2097152 -> [248, 136, 128, 128, 128]
30606638 -> [249, 180, 176, 148, 174]
67108863 -> [251, 191, 191, 191, 191]
67108864 -> [252, 132, 128, 128, 128, 128]
20566519621 -> [254, 147, 137, 183, 130, 189, 133]
68719476735 -> [254, 191, 191, 191, 191, 191, 191]
68719476736 -> [255, 129, 128, 128, 128, 128, 128, 128]
1731079735717 -> [255, 153, 140, 140, 153, 136, 166, 165]
2199023255551 -> [255, 159, 191, 191, 191, 191, 191, 191]
2199023255552 -> [255, 160, 160, 128, 128, 128, 128, 128, 128]
64040217759022 -> [255, 174, 163, 186, 134, 155, 164, 180, 174]
70368744177663 -> [255, 175, 191, 191, 191, 191, 191, 191, 191]
70368744177664 -> [255, 176, 144, 128, 128, 128, 128, 128, 128, 128]
34369578119952639221217025744100729453590194597032 -> [255, 191, 191, 191, 191, 165, 184, 145, 129, 139, 182, 177, 159, 176, 167, 155, 139, 159, 138, 163, 170, 143, 151, 141, 156, 154, 134, 183, 176, 175, 170, 178, 168]

```

# Answer
> 5 votes
# Charcoal, 47 bytes

```
Ｎθ≔÷⁺³Ｌ↨θ²¦⁵ηＩ⎇‹θ¹²⁸θＥ↨⁺θ⁻Ｘ⁶⁴η×⁴Ｘ³²η⁶⁴⁺ι×⁶⁴⁺²¬κ

```

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

```
Ｎθ

```

Input the integer.

```
≔÷⁺³Ｌ↨θ²¦⁵η

```

Calculate the number of bytes the extended representation would take.

```
Ｉ⎇‹θ¹²⁸θ

```

If the integer is less than 128 then just output the integer again, otherwise...

```
Ｅ↨⁺θ⁻Ｘ⁶⁴η×⁴Ｘ³²η⁶⁴⁺ι×⁶⁴⁺²¬κ

```

... calculate `n-2` high-level bits, add that to the integer, convert to base `64`, then add `192` to the first byte and `128` to the remaining bytes.

# Answer
> 4 votes
# JavaScript (Node.js),  ~~104~~  103 bytes

*Saved 1 byte thanks to @emanresuA*

Expects a BigInt. Returns a comma-separated string of bytes.

```
n=>n>127?(g=k=>k>63?g(k>>6n)+[,k&63n|128n]:k|192n)(2n**(x=(h=n=>n?-~h(n/2n):3n)(n)/5n)-4n<<x*5n|n):n+''

```

Try it online!

### 92 bytes

An alternate version taking a standard JS number. It only works up to 0x3FFFFFF, which somewhat defeats the purpose of using UTF-∞. :-/

```
n=>n>>7?(g=k=>k>>6?g(k>>6)+[,k&63|128]:k|192)(2**(x=(h=n=>n?-~h(n>>1):3)(n)/5|0)-4<<x*5|n):n

```

Try it online!

### How?

This is essentially the same method as @Neil's.

Using the recursive function \\$h\\$, we compute \\$x=\left\lfloor(b+3)/5\right\rfloor\\$, where \\$b\\$ is the number of bits in the input.

We compute \\$2^x-4\\$ (a bit mask consisting of \\$x-2\\$ ones followed by \\$2\\$ zeros). We shift it by \\$5x\\$ positions to the left and OR it with \\$n\\$.

Using the recursive function \\$g\\$, we convert the result to base \\$64\\$ in big-endian order. We add \\$192\\$ to the leading byte and \\$128\\$ to the other ones.

# Answer
> 3 votes
# JavaScript (Node.js), 171 bytes

```
n=>n<128?n:(F='0bxxxxxxxx '.repeat(c=((d=n.toString(2)).length+3)/5|0)[r='replace'](/ 0bxx/g,' 0b10',i=0))[r](/x/g,_=>i++<c?1:d.padStart(5*c+3,0)[i-c])[r](/0b\d{8}/g,eval)

```

Try it online!

Since `n<128` is an edgecase, just handle it there and then.

Next, the code determines the number of bytes using a simple formula: if there are `c` bytes, then there are `5c+1` x's, so we use that. This means subtracting one from the number of bits in the binary representation and dividing that by five. We repeat `xxxxxxxx`  that many times. Replace the first two x's of any byte that is not the first with a `10`, then replace the remaining x's with the (padded) binary representation of `n`, then evaluate each byte.

Output format: as a number for `n<128`, as a space-separated string (with trailing newline) otherwise. Let me know if this is not allowed.

Fails on last testcase due to JavaScript's limitations.

*Thanks @Neil for -7 bytes.*

# Answer
> 2 votes
# JavaScript (Node.js), 137 bytes

```
n=>n<128?[n]:eval(`[0b${('1'.repeat((L=(s=n.toString(2)).length+3)/5)+'0'.repeat(~(4.8*~L%6-2))+s).match(/^.{8}|.{6}/g).join`n,0b10`}n]`)

```

Try it online!

StackExchange code highlight is broken again... Not sure if using string based idea could golf some more bytes or not.

# Answer
> 1 votes
# 05AB1E, 33 bytes

```
žy@ibg3+5÷U64Xm32Xm4*-+64вāΘÌ64*+

```

Port of *@Neil*'s Charcoal answer.

Try it online or verify all test cases.

**Explanation:**

In pseudo-code:

For inputs \\$\<128\\$, simply output the input
For inputs \\$\geq128\\$:

1. With \\$n\\$ as input, first calculate: \\$x=\left\lfloor\frac{len(bin(n))+3}{5}\right\rfloor\\$
2. Then calculate \\$y=64^x-4\times32^x+n\\$
3. Convert this \\$y\\$ to a base-64 list
4. Add 128 to each item, and an additional 64 to the very first item, which is the intended output

```
žy@i             # If the (implicit) input-integer is >= 128:
    b            #  Convert the (implicit) input to a binary string
     g           #  Pop and push its length
      3+         #  Add 3
        5÷       #  Integer-divide that by 5
          U      #  Pop and store it in variable `X`
    64Xm         #  Push 64 to the power `X`
        32Xm     #  Push 32 to the power `X`
            4*   #  Multiply it by 4
              -  #  Subtract it from each other
               + #  Add the (implicit) input to it
    64в          #  Convert this integer to a base-64 list
       ā         #  Push a list in the range [1,length] (without popping)
        Θ        #  Convert every non-1 to 0 (with an ==1 check)
         Ì       #  Add 2 to each
          64*    #  Multiply each by 64
             +   #  Add the values at the same positions in the lists together
                 #  (after which this list is output implicitly as result)
                 # (implicit else:)
                 #  (implicitly output the implicit input)

```

# Answer
> 0 votes
# JavaScript (Node.js), 101 bytes

```
n=>(h=x=>x>>8n?[...h(x>>6n),x%64n+128n]:[x])((g=x=>n>>7n?n>>1n+5n*x?g(++x):64n**x-32n**x:x)(0n)*4n+n)

```

Try it online!

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