Single Digit Representations of Natural Numbers

Question

Task

Write a program/function that when given a positive integer \$n\$ and a digit \$d\$ which is not 0 outputs a way to represent \$n\$ using only addition, subtraction, multiplication, exponentiation, division, concatenation, parenthesis and the digit \$d\$.

Examples

n =  6, d = 1  =>  (1 + 1) * (1 + 1 + 1)
n =  6, d = 1  =>  1 + 1 + 1 + 1 + 1 + 1
n = 10, d = 1  =>  1 || 1 - 1
n = 12, d = 1  =>  1 || (1 + 1)
n = 64, d = 2  =>  2 ^ (2 + 2 + 2)
n =  1, d = 9  =>  9 / 9

Note: In the examples || represents concatenation

Output Format

• Concatenation must be explicit with a separate operator
• Output can be a string, list of operations and numbers or a list of lists in place of brackets.
• You may choose the precedence of the operators but it must be consistent for all outputs produced by your program/function
• Output may be in polish, reverse polish or infix notation but it must be consistent for all outputs produced by your program/function.
• You can use custom symbols for representing the digits and operations but the symbols used for representing the digits and operations should be distinct.

Scoring

This is code-challenge, Your score will be

100*B + S

Where B is the number of bytes in the program/function, and S is the sum of the number of times the digit \$d\$ appears in the representation of \$n\$ with the digit \$d\$ as returned by your program/function for all \$n \le 1000\$ and all \$d\$ from 1 to 9

Lowest score wins

Example: if your program is abcd and all representation of \$n\$ returned by your program has 5 occurrences of \$d\$ then its score will be (4 * 100) + (5 * 1000 * 9) = 45400

Rules

• Your program/function should run deterministically, so that it always returns the same representation for a given \$n\$ and \$d\$ (and hence always gets the same score).
• Your answer must include not only your submission, but also the code you used to calculate the S part of its score. This need not be written in the same language as your submission, and will not be counted towards its byte count. You are encouraged to make it readable.
• Your answer must include the precedence of the operators needed to evaluate the outputs produced by your program/function
• You must actually run your test program and calculate/verify your score before submitting your entry. If your submission runs too slowly for you to verify its score then it is not qualified to compete, even if you know what its score would be in principle.

---

Inspired by this video

Answer 1

Python 3, 210 bytes · 100 + 59045 digits = 80045

def f(n,d):
 m={d:d},
 while{n}-{*m[0]}:m={z:(p[x],o,q[y])for p,q in zip(m,m[::-1])for x in p for y in q for z,o in zip([x+y,x-y,x*y,y<9and x**y,x%y<1and x//y,int(f"{x}{y}")],"+-*^/|")if z>0},*m
 return m[0][n]

Try it online!

Scoring

Scoring goes much faster using this modified version that solves 1 through 1000 all at once:

def f_gen(d):
 m={d:d},
 while 1:yield from m[0].items();m={z:(p[x],o,q[y])for p,q in zip(m,m[::-1])for x in p for y in q for z,o in zip([x+y,x-y,x*y,y<9and x**y,x%y<1and x//y,int(f"{x}{y}")],"+-*^/|")if z>0},*m

def size(expr):
    return 1 if isinstance(expr, int) else size(expr[0]) + size(expr[2])

score = 0
for d in range(1, 10):
    s = set(range(1, 1001))
    for n, expr in f_gen(d):
        if n in s:
            s -= {n}
            score += size(expr)
            print(n, expr)
            if not s:
                break
print(score)

Answer 2

JavaScript (Node.js), Score:  87900 ... 83274  82574

229 bytes x 100 + 59674 digits

Takes input as (d)(n). Returns a string. Uses | for concatenation.

d=>n=>[0,v=[d],F={[d]:d},s={[d]:0}].map(_=>v.map(x=>v.map(y=>[x+y,x-y,x*y,x/y,x**y,[x]+y].map((z,o)=>z<0|z>1e4||z%1?0:(!F[z]&&V.push(+z))|(S=s[x]-~s[y])<s[z]?F[s[z]=S,z]=`(${F[x]+'+-*/^|'[o]+F[y]})`:0)),V=[])&&v.push(...V))&&F[n]

Try it online!

Scoring

Because the golfed version is quite slow, the total score was computed with the following ungolfed version which, given \$d\$, computes the formulas for all \$n\in[1..1000]\$ at once.

Although it works on TIO, the output is too long. So the link below is an example for \$d=9\$.

Try it online!

const OP = ['+', '-', '*', '/', '^', '||'];

function solve(d) {
  let value = [ d ],
      formula = { [d] : d },
      size = { [d] : 0 },
      total = 0;

  for(let i = 0; i < 4; i++) {
    let newValue = [];

    value.forEach(x => {
      value.forEach(y => {
        [0, 1, 2, 3, 4, 5].forEach(o => {
          let v;

          switch(o) {
            case 0: v = x + y; break;
            case 1: v = x < y ? null : x - y; break;
            case 2: v = x * y; break;
            case 3: v = x % y ? null : x / y; break;
            case 4: v = x ** y; break;
            case 5: v = +(x.toString() + y.toString()); break;
          }

          if(v !== null && v <= 10000) {
            let sz = size[x] + size[y] + 1;

            if((formula[v] === undefined && newValue.push(v)) || sz < size[v]) {
              formula[v] = '(' + formula[x] + OP[o] + formula[y] + ')';
              size[v] = sz;
            }
          }
        });
      });
    });
    value.push(...newValue);
  }

  for(let n = 1; n <= 1000; n++) {
    console.log(n, size[n] + 1, formula[n]);
    total += size[n] + 1;
  }
  console.log('-->', total);
  return total;
}

let score = 0;

for(let d = 1; d <= 9; d++) {
  score += solve(d);
}
console.log('Final score:', score);

Answer 3

Wren, 107 bytes, score: 138373

Thanks to @Mukundan for the golfing so far!

(This answer was written before @GammaFunction did so.)

Fn.new{|n,d|"%(n)".map{|i|Num.fromString(i)}.map{|i|i<1?[d,-d]:[d]*(i/d).floor+["%(d)/%(d)"]*(i%d)}.join()}

Try it online!

Answer 4

Brainfuck, 30 bytes * 100 + 9009000 = 9012000

Uses the fact that n = (d/d)*n:

,>,>+<<->.>.<.<[->>>.<<.>.<.<]

In that program, the character representing division is ASCII 1 and the character representing addition is ASCII 0, so the output isn't very readable.

With this TIO link I include a brief header making the output readable. There is still the minor inconvenience that input are ASCII characters (the link has a new line, ASCII 10, in the input, hence the program prints

9/9+9/9+9/9+9/9+9/9+9/9+9/9+9/9+9/9+9/9

To make 10. If instead you use this interpreter, you can type easier to understand input, using \ to insert the values of the ascii characters, instead of using the ascii characters. So, using \10\57 as input in this program gives the same result as the program on TIO.

Answer 5

Zsh, 89 81 75 bytes, score: 135173

(total digit count is 127673)

for c (${(s::)1})(repeat c/$2 s+=($2);repeat c%$2 s+=($2/$2);<<<${s=$2-$2})

Try it online!

(This generates the same operations that @a'_''s method does. I thought of it independently, then saw his score using it, then implemented it.)

You can use custom symbols for representing the digits and operations [...]

We take advantage of that here; concatenation is represented by a newline and addition is represented by space. Concatenation has lower precedence than addition, which has lower precedence than division.

for c (${(s::)1})(          # for each digit c in n
                            # repeat $x expands $x in arithmetic mode
    repeat c/$2 s+=($2)     # append d to $s, c/d times
    repeat c%$2 s+=($2/$2)  # append d/d to $s, c%d times 
    <<<${s=$2-$2}           # if $s is still unset, set it to d-d
                            # <<< prints $s, implicitly joined on spaces
)                           # exit the subshell, effectively unsetting $s

Answer 6

Charcoal, 150 bytes × 100 + 81773 digits = 96773

⪫Ｅθ§⪪§⪪”}∧⟦NＪgＹＺＧ；|⪫v4⌈-LiςΠg➙∨Ｃ⊕⊙Nψ≧Fδ∨↧↧«3Ｙ!‴2ⅈ⸿⟦⁰J◨(⁴⦄4b¶¤⦄→₂⊞GςＧ⸿≡←ε⭆R？ρq＆Σ<×HJ⁶�⧴Q<"k~3Ｖu⌊+ＬΠ↓1βπt“P³∨Ｒ▶Ａ↓ⅉs▷"«‖κ-σ_←U/Ｖ!Ｕ⊕⁷↙Ｕ3M⁼³ＲＶＶ¤HＱ:”;Ｉη,Ｉι&

Try it online! Link is to verbose version of code. Uses & (low precedence) as concatenation and # to represent the input digit. Explanation: Simply looks up all of the digit patterns in a (compressed) hand-crafted lookup table and concatenates the relevant digits together. Proof of digit count.

Answer 7

W n, 22 bytes * 100 + 127673 = 129 873

A blatant rip-off of my Wren answer.

☺◘Y╔û çτ◘↑═uon↕I6≡ÿÑ°t

Uncompressed:

1,             % Split number to chunks of 1
  c}           % Construct the list [input]
    ac/*       %   Repeat that input/current times
  c:{          % The list [input,input]
     '/,       % The string input/input
        }      % The list [input/input]
         acm*  %   Repeat that list input%current times
             + % Join these two lists
      |        % If that's the empty list:
  c:_{         %   Yield the list [input,-input]
       M       % Do that for every thing in the input

Answer 8

Ruby, Score: 127,473 (178 bytes * 100 + 109,673)

->n,d{n.to_s.chars.map{|c|g=d.to_s;c<?1?g+?-+g:(i=c.to_i)==d ?d:(d*d==i)?g+?*+g:i%d<1?([d.to_s]*(i/d))*?+:i>d ?g+?++f[i-d,d]:(i+1==d&&i>1)?g+?-+f[d-i,d]:[d==1?d:g+?/+g]*i*?+}*?|}

Try it online!

This uses | as concatenation. It could also definitely be cleverer. I just kept adding cases to try to minimse the occurences of d.