21
\$\begingroup\$

This code challenge will have you compute the number of ways to reach \$n\$ starting from \$2\$ using maps of the form \$x \mapsto x + x^j\$ (with \$j\$ a non-negative integer), and doing so in the minimum number of steps.

(Note, this is related to OEIS sequence A307092.)

Example

So for example, \$f(13) = 2\$ because three maps are required, and there are two distinct sequences of three maps that will send \$2\$ to \$13\$:

$$\begin{array}{c} x \mapsto x + x^0 \\ x \mapsto x + x^2 \\ x \mapsto x + x^0\end{array} \qquad \textrm{or} \qquad \begin{array}{c}x \mapsto x + x^2 \\ x \mapsto x + x^1 \\ x \mapsto x + x^0\end{array}$$

Resulting in \$2 \to 3 \to 12 \to 13\$ or \$2 \to 6 \to 12 \to 13\$.

Example values

f(2)   = 1 (via [])
f(3)   = 1 (via [0])
f(4)   = 1 (via [1])
f(5)   = 1 (via [1,0])
f(12)  = 2 (via [0,2] or [2,1])
f(13)  = 2 (via [0,2,0] or [2,1,0], shown above)
f(19)  = 1 (via [4,0])
f(20)  = 2 (via [1,2] or [3,1])
f(226) = 3 (via [2,0,2,1,0,1], [3,2,0,0,0,1], or [2,3,0,0,0,0])
f(372) = 4 (via [3,0,1,0,1,1,0,1,1], [1,1,0,2,0,0,0,1,1], [0,2,0,2,0,0,0,0,1], or [2,1,0,2,0,0,0,0,1])

Challenge

The challenge is to produce a program which takes an integer \$n \ge 2\$ as an input, and outputs the number of distinct paths from \$2\$ to \$n\$ via a minimal number of maps of the form \$x \mapsto x + x^j\$.

This is , so fewest bytes wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think it should be explicitly noted that the ^ symbol denotes exponentiation. It could be XOR as well (for instance C uses ^ for bitwise XOR). \$\endgroup\$ – Ramillies Aug 26 at 13:01
  • 1
    \$\begingroup\$ @Ramillies Maybe it should be changed to MathJax. I.e. \$x=x+x^j\$ instead of x -> x + x^j. \$\endgroup\$ – Kevin Cruijssen Aug 26 at 13:33
  • \$\begingroup\$ @KevinCruijssen: Good point, that would certainly help. \$\endgroup\$ – Ramillies Aug 26 at 13:37
  • \$\begingroup\$ I have added this to the OEIS as A309997. (It will be a draft until approved.) \$\endgroup\$ – Peter Kagey Aug 26 at 19:48

10 Answers 10

2
\$\begingroup\$

Jelly, 16 bytes

2+*¥þ³Ḷ¤F$n³Ạ$¿ċ

Try it online!

A full program taking as its argument \$n\$ and returning the number of ways to reach \$n\$ using the minimal path length. Inefficient for larger \$n\$.

\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6),  111 ... 84  80 bytes

Returns true rather than \$1\$ for \$n=2\$.

f=(n,j)=>(g=(i,x,e=1)=>i?e>n?g(i-1,x):g(i-1,x+e)+g(i,x,e*x):x==n)(j,2)||f(n,-~j)

Try it online!

Commented

f = (                     // f is the main recursive function taking:
  n,                      //   n = input
  j                       //   j = maximum number of steps
) => (                    //
  g = (                   // g is another recursive function taking:
    i,                    //   i = number of remaining steps
    x,                    //   x = current sum
    e = 1                 //   e = current exponentiated part
  ) =>                    //
    i ?                   // if there's still at least one step to go:
      e > n ?             //   if e is greater than n:
                          //     add the result of a recursive call with:
        g(i - 1, x)       //       i - 1, x unchanged and e = 1
      :                   //   else:
                          //     add the sum of recursive calls with:
        g(i - 1, x + e) + //       i - 1, x + e and e = 1
        g(i, x, e * x)    //       i unchanged, x unchanged and e = e * x
    :                     // else:
      x == n              //   stop recursion; return 1 if x = n
)(j, 2)                   // initial call to g with i = j and x = 2
|| f(n, -~j)              // if it fails, try again with j + 1
\$\endgroup\$
4
\$\begingroup\$

Haskell, 78 75 bytes

This implementation uses a breath-first-search in the "tree" of iteratively all necessary mappings x -> x + x^j.

j#x=x+x^j
f n=[sum[1|x<-l,x==n]|l<-iterate((#)<$>[0..n]<*>)[2],n`elem`l]!!0

Try it online!

Explanation

-- computes the mapping x -> x + x^j
j#x=x+x^j                          
--iteratively apply this function for all exponents [0,1,...,n] (for all previous values, starting with the only value [2])
                            iterate((#)<$>[0..n]<*>)[2] 
-- find each iteration where our target number occurs
    [                   |l<-...........................,n`elem`l] 
-- find how many times it occurs
     sum   [1|x<-l,x==n] 
-- pick the first entry
f n=.............................................................!!0
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 17 bytes

2¸[˜DIå#εIÝmy+]I¢

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 2, 72 bytes

f=lambda n,l=[2]:l.count(n)or f(n,[x+x**j for x in l for j in range(n)])

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Nice way of implementing BFS recursively. \$\endgroup\$ – Joel Aug 27 at 3:30
1
\$\begingroup\$

Perl 5 (-lp), 79 bytes

$e=$_;@,=(2);@,=map{$x=$_;map$x+$x**$_,0..log($e)/log$x}@,until$_=grep$_==$e,@,

TIO

\$\endgroup\$
1
\$\begingroup\$

CJam (27 bytes)

qi2a{{_W$,f#f+~2}%_W$&!}ge=

Online demo

Warning: this gets very memory-intensive very fast.

Dissection:

qi            e# Read input and parse to int n (accessed from the bottom of the stack as W$)
2a            e# Start with [2]
{             e# Loop
  {           e#   Map each integer x in the current list
    _W$,f#f+~ e#     to x+x^i for 0 <= i < n
    2         e#   and add a bonus 2 for the special case
  }%          e#   Gather these in the new list
  _W$&!       e#   Until the list contains an n
}g
e=            e# Count occurrences

The bonus 2s (to handle the special case of input 2, because while loops are more expensive than do-while loops) mean that the size of the list grows very fast, and the use of exponents up to n-1 means that the values of the larger numbers in the list grow very fast.

\$\endgroup\$
1
\$\begingroup\$

Haskell, 65 bytes

([2]%)
l%n|elem n l=sum[1|x<-l,x==n]|1>0=[x+x^k|x<-l,k<-[0..n]]%n

Try it online!

Golfing flawr's breadth-first-search. I also tried going backwards from n, but it was longer:

73 bytes

q.pure
q l|elem 2l=sum[1|2<-l]|1>0=q[x|n<-l,x<-[0..n],i<-[0..n],x+x^i==n]

Try it online!

\$\endgroup\$
1
\$\begingroup\$

R, 78 77 bytes

function(n,x=2){while(!{a=sum(x==n)})x=rep(D<-x[x<n],n+1)+outer(D,0:n,'^')
a}

Try it online!

Using a simplified Breadth-first Search

Unrolled code with explanation :

function(n){                              # function taking the target value n

  x=2                                     # initialize vector of x's with 2

  while(!(a<-sum(x==n))) {                # count how many x's are equal to n and store in a
                                          # loop while a == 0

    x=rep(D<-x[x<n],n+1)+outer(D,0:n,'^') # recreate the vector of x's 
                                          # with the next values: x + x^0:n
  }
a                                         # return a
}   

Shorter version with huge memory allocation (failing for bigger cases) :

R, 70 69 bytes

function(n,x=2){while(!{a=sum(x==n)})x=rep(x,n+1)+outer(x,0:n,'^')
a}

Try it online!

-1 byte thanks to @RobinRyder

\$\endgroup\$
  • \$\begingroup\$ !(a<-sum(x==n)) could be !{a=sum(x==n)} for -1 byte in both cases. \$\endgroup\$ – Robin Ryder Sep 6 at 8:37
0
\$\begingroup\$

Pyth, 24 bytes

VQIJ/mu+G^GHd2^U.lQ2NQJB

Try it online!

This should produce the correct output, but is very slow (the 372 test case times out on TIO). I could make it shorter by replacing .lQ2 with Q, but this would make the runtime horrendous.

Note: Produces no output for unreachable numbers \$(n \leq 1)\$

Explanation

VQ                        # for N in range(Q (=input)):
   J                      #   J =
     m                    #     map(lambda d:
      u                   #       reduce(lambda G,H:
       +G^GH              #         G + G^H,
            d2            #         d (list), 2 (starting value) ),
              ^U.lQ2N     #       cartesian_product(range(log(Q, 2)), N)
    /                Q    #     .count(Q)
  IJ                  JB  #   if J: print(J); break
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.