Factoriadic Fraction Addition

Question

Objective

Given two rational numbers represented in fractional factoriadic as defined below, add them, and output the result in fractional factoriadic.

Fractional factoriadic

Fractional factoriadic is a numeral system that represents every rational number using \$1/2\$'s place, \$1/6\$'s place, \$1/{24}\$'s place and so on (in general, \$1/{n!}\$'s place for each integer \$n \geq 2\$), with these digits of choice:

• The digit at \$1/2\$'s place may be any integer.
• The digit at \$1/6\$'s place may be \$0\$, \$1\$ or \$2\$.
• The digit at \$1/{24}\$'s place may be \$0\$, \$1\$, \$2\$, or \$3\$.
• The digit at \$1/{120}\$'s place may be \$0\$, \$1\$, \$2\$, \$3\$, or \$4\$.
• Ad infinitum. In general, for every integer \$n \geq 3\$, the digit at \$1/{n!}\$'s place may be from \$0\$ to \$n-1\$ inclusive.

Mathematical remarks

Fractional factoriadic identifies \$\mathbb{Q}\$ as the direct limit of the following inclusion sequence in the category of abelian groups: $$ \langle 1/2 \rangle \to \langle 1/6 \rangle \to \langle 1/{24} \rangle \to \langle 1/{120} \rangle \to \langle 1/{720} \rangle \to \cdots $$

I/O format

It is assumed that the inputted fractions are MSD-first and have no trailing zeros. This applies to the output also.

Examples

Fraction = intermediate representation = fractional factoriadic

0 = 0/2 = []
1 = 2/2 = [2]
2 = 4/2 = [4]
3/2 = 3/2 = [3]
-1/2 = -1/2 = [-1]
1/3 = 2/6 = [0, 2]
1/4 = 1/6 + 2/24 = [0, 1, 2]
2/3 = 1/2 + 1/6 = [1, 1]
3/4 = 1/2 + 1/6 + 2/24 = [1, 1, 2]
1/5 = 1/6 + 4/120 = [0, 1, 0, 4]
-1/4 = -1/2 + 1/6 + 2/24 = [-1, 1, 2]
7/3 = 4/2 + 2/6 = [4, 2]

[] + [] = []
[] + [1] = [1]
[0, 2] + [-1] = [-1, 2]
[0, 2] + [0, 2] = [1, 1]
[0, 1, 2] + [0, 1, 2] = [1]

Answer 1

Nekomata + -1, 18 bytes

+:#ᵑ{CU$x3+þç++;ž¿

Attempt This Online!

+:#ᵑ{CU$x3+þç++;ž¿
+                   Add two lists; pad with 0s
                    e.g. [0,2] [-1] -> [-1,2]
 :                  Duplicate
  #                 Length
   ᵑ{               Repeat the following function that many times:
     CU$                Split into the head and the rest
                        e.g. [0,2,4] -> [0] [2,4]
        x3+             Push [3,...,length+2]
                        e.g. [0] [2,4] -> [0] [2,4] [3,4]
           þ            Divmod; get the quotient and the remainder
                        e.g. [0] [2,4] [3,4] -> [0] [0,1] [2,0]
            ç           Prepend 0 to the remainder
                        e.g. [0] [0,1] [2,0] -> [0] [0,1] [0,2,0]
             ++         Add the three lists
                        e.g. [0] [0,1] [0,2,0] -> [0,3,0]
               ;ž¿      Remove some trailing 0s
                        e.g. [0,3,0] -> [0,3]

The last step ;ž¿ is nondeterministic, so we need to add the -1 flag to return only the first result, where all trailing 0s are removed.

Answer 2

R, 125 bytes

\(v,w,`^`=c,y=w^0,s=seq){a=(!s(x<-v^0)-(e=s(x+y)))*x+y*!s(y)-e
while(any(a-(a=a-(b=(a>e))*e-b+b[-1]^0)))1
a[s(l=max(e*!!a))]}

Attempt This Online!

How? - ungolfed version:

add_factoriadic=function(x,y){
    a<-c(x,y,0)&0                             # define a as long-enough vector of zeros 
    a[seq(!x)]=x                              # add x to appropriate elements
    a[seq(!y)]=a[seq(!y)]+y                   # add y to appropriate elements
    while({                                   # repeat while value of a changes:
        b=(a>seq(a))                          #   b = carry digits
        any(a-                                #   check whether a changes by
          (a=a+c(b[-1],0)                     #     add carry digits at position to left
              -b*(seq(a)+1)))                 #     and subtract carried values
    })1                                       #   (do nothing else)
    a[seq(length=max(seq(a)*!!a))]            # finally, output a without trailing zeros
}

Answer 3

Jelly, 17 bytes

+dṛ¦J‘$F+2/ƲÐLœr0

A dyadic Link that accepts factoriadic fractions as lists of integers on each side and yields their sum.

Try it online! Or see the test-suite.

How?

Repeated carrying...

+dṛ¦J‘$F+2/ƲÐLœr0 - Link: integer list, [a,b,c,...]; integer list, [x,y,z,...]
+                 - {A} add {B} (vectorises) -> S = [a+x, b+y, c+z, ...]
            ÐL    - repeat until the results are no longer unique:
           Ʋ      -   last four links as a monad:
      $           -     last two links as a monad:
    J             -       indices -> [1,2,...N]
     ‘            -       increment -> I = [2,3,...,N+1]
   ¦              -     sparse application (to {V in S} with {i in I})...
  ṛ               -     ...to indices: right argument = I
                           i.e. apply to all but the first element
 d                -     ...action: {V} divmod {i} -> [V//i, V%i]
       F          -     flatten -> [a+x, (b+y)//3, (b+y)%3, (c+z)//4, (c+z)%4, ...]
         2/       -     2-wise reduce by:
        +         -       addition -> [a+x+(b+y)//3, (b+y)%3+(c+z)//4, ...]
              œr0 - trim trailing zeros

Answer 4

APL(Dyalog Unicode), 35 bytes ^SBCS

Assumes index origin 0.

{x↓⍨-⊥⍨0=x←(⊢⊤⊥∘m)(⊢+2××)⍳≢m←+⌿↑⍺⍵}

Try it on APLgolf!

Add the inputs element-wise, convert back and forth using mixed base 0 3 4 5 ..., drop trailing zeros.

Answer 5

JavaScript (Node.js), 93 bytes

f=([a=0,...A],[b=c=0,...B],i)=>k=A+B||a|b?f(A,B,i+1||2)!=-(b+=c+a,c=b>i,b+=c*~i)?[b,...k]:k:A

Try it online!

==- if former is [] and latter is 0. Former is never negative and latter, including -, is never positive

Answer 6

Charcoal, 57 bytes

Ｆ⁻ＬηＬθ⊞θ⁰≔⁰ζＦ⮌Ｅηκ«≧⁺⁺§θι⊟ηζ§≔θι⎇ι﹪ζ⁺²ιζ≧÷⁺²ιζ»Ｗ∧θ¬↨θ⁰⊟θＩθ

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

Ｆ⁻ＬηＬθ⊞θ⁰

Extend the first input to the length of the second.

≔⁰ζ

Start with no carry.

Ｆ⮌Ｅηκ«

Enumerate the indices of the second array in reverse.

≧⁺⁺§θι⊟ηζ

Add the values in the two array elements to the carry.

§≔θι⎇ι﹪ζ⁺²ιζ

Update the output value, reducing modularly if necessary.

≧÷⁺²ιζ

Update the carry.

»Ｗ∧θ¬↨θ⁰⊟θ

Remove any trailing zeros.

Ｉθ

Output the final result.

Bonus 136-byte Retina 0.8.2 solution: Try it online! Does not work with negative numbers.

Answer 7

Wolfram Language (Mathematica), 71 bytes

If[#==0,{},{a=⌊++j#⌋,##&@@#0[j#-a]}]&@Tr[Tr[i=j=1;#/++i!&/@#]&/@#]&

Try it online!

Input [{numbers...}].

                                        Tr[i=  1;#/++i!&/@#]&/@#   from factoriadic
                                     Tr[                        ]  sum
If[#==0,{},{a=⌊++j#⌋,##&@@#0[j#-a]}]&@       j=1                   to factoriadic

Answer 8

JavaScript (Node.js), 166 bytes

(a,b)=>{b.map((x,i)=>a[i]=(a[i]?a[i]:0)+x);c=0;for(i=(y=a.length)-1;i>0;i--){d=(e=a[i]+c)%(z=i+2);c=e/z|0;a[i]=d};y?a[0]+=c:0;while(a[a.length-1]==0)a.pop();return a}

Try it online!

Expanded, with comments:

(a,b)=>{
b.map((x,i)=>a[i]=(a[i]?a[i]:0)+x); //add elements in arrays a and b, 
                                    //allowing for different size arrays.

c=0;                                //initialize carry

for(i=(y=a.length)-1;i>0;i--){      //adjust each value so it fits within the max
                                    //for that digit, 
                                    //carrying to the left as required.

d=(e=a[i]+c)%(z=i+2);               //use mod for the digit

c=e/z|0;                            //use divide and round for the carry

a[i]=d                              //put the digit back in the array

};

y?a[0]+=c:0;                        //add remaining carry to the first digit

while(a[a.length-1]==0)a.pop();     //remove trailing zeros

return a //return result

}

Answer 9

Setanta, 175 153 150 146 bytes

gniomh(x,y){z:=x+[0]*(fad@y-fad@x)le i idir(0,fad@y)z[i]+=y[i]le i idir(fad@z-1,0)ma i+1{z[i-1]+=z[i]//(i+2)z[i]%=i+2z[i]|scrios_cul@z()}toradh z}

try-setanta.ie link

Answer 10

05AB1E (legacy), 16 bytes

ζOāvćsā̉‚˜2ôO0Ü

First halve of the program is a port of @alephalpha's Nekomata's answer and the second halve is a port of @JonathanAllan's Jelly answer, so make sure to upvote both those answers as well!

Input as a pair of lists.

Try it online or verify all test cases.

Explanation:

Uses the legacy version of 05AB1E so it won't need an additional leading 0, since invalid characters in a list when summing (a space in this case) are simply ignored in the legacy version.

ζ                # Zip/transpose the (implicit) input-pair; swapping rows/columns,
                 # using an implicit space " " as filler for unequal length rows
 O               # Sum each inner list, ignoring the spaces
  ā              # Push a list in the range [1,length] (without popping)
   v             # Pop and loop over those items (without using them),
                 # aka, `āv` is used to loop the length amount of times:
    ć            #  Extract head; push first item and remainder-list separately
     s           #  Swap so the remainder-list is at the top of the stack
      ā          #  Push a list in the range [1,length] (without popping)
       Ì         #  Increase each by 2 to make the range [3,length+2]
        ‰        #  Divmod the remainder-list by this [3,length+2]-list
         ‚       #  Pair it with the extracted head
          ˜      #  Flatten this list
           2ô    #  Split it into pairs
             O   #  Sum each pair
              0Ü #  Trim any trailing 0s
                 # (after the loop, the resulting list is output implicitly)