20
\$\begingroup\$

We know that f is a polynomial with non-negative integer coefficients.

Given f(1) and f(1+f(1)) return f. You may output f as a list of coefficients, an ASCII formatted polynomial, or similar.

Examples:

f(1)  f(1+f(1))  f
0     0          0
1     1          1
5     75         2x^2 + 3
30    3904800    4x^4 + 7x^3 + 2x^2 + 8x + 9
1     1073741824 x^30
\$\endgroup\$
  • 1
    \$\begingroup\$ Random question: I'm too tired to try to prove/disprove this right now, but is it guaranteed that we will always be able to get an answer from f(1) and f(1+f(1))? \$\endgroup\$ – HyperNeutrino Mar 30 '17 at 3:13
  • 4
    \$\begingroup\$ @HyperNeutrino I wouldn't have made this challenge otherwise. \$\endgroup\$ – orlp Mar 30 '17 at 3:16
  • \$\begingroup\$ Right, that is a good point. Hm. Interesting, I will look into proving that tomorrow because that's very interesting. Thanks for the interesting challenge! \$\endgroup\$ – HyperNeutrino Mar 30 '17 at 3:18
  • 1
    \$\begingroup\$ The base-conversion tag is supposed to be a hint? \$\endgroup\$ – Thunda Mar 30 '17 at 3:25
  • 9
    \$\begingroup\$ As much as this is a cute puzzle, I think the code is basically base conversion. Possibly dupe? \$\endgroup\$ – xnor Mar 30 '17 at 3:34
27
\$\begingroup\$

Jelly, 3 bytes

‘b@

Try it online!

Returns the polynomial as a list of coefficients.

Since we know the polynomial has non-negative integer coefficients, f(b) can be interpreted as "the coefficients of the polynomial, taken as base b digits," by the definition of a base. This is subject to the condition that none of the coefficients exceeds or is equal to b, but we know that, because b is one greater than the sum of the coefficients (which is f(1)).

The program simply increments the first argument () to get 1+f(1), then calls the base convertion atom (b) with the first argument as the base and the second argument as the number (using @ to swap the order of the arguments, since b usually takes the number first and base second).

This was quite the clever challenge; thanks orlp!

\$\endgroup\$
  • 13
    \$\begingroup\$ How in the world is this possible \$\endgroup\$ – Thunda Mar 30 '17 at 3:30
  • \$\begingroup\$ I need to learn jelly... \$\endgroup\$ – sagiksp Mar 30 '17 at 5:12
  • \$\begingroup\$ Dennis has to see this one for sure. \$\endgroup\$ – Erik the Outgolfer Mar 30 '17 at 11:54
6
\$\begingroup\$

Mathematica, 29 28 bytes

Thanks to JungHwan Min for saving 1 byte! (ironically, with a Max)

#2~IntegerDigits~Max[#+1,2]&

Pure function taking two nonnegative integers and returning a list of (nonnegative integer) coefficients. #2~IntegerDigits~(#+1) would be the same algorithm as in Doorknob's Jelly answer; unfortunately, Mathematica's IntegerDigits chokes when the base equals 1, hence the need for extra bytes Max[...,2].

\$\endgroup\$
  • 2
    \$\begingroup\$ Haha, nice one. \$\endgroup\$ – JungHwan Min Mar 30 '17 at 7:56
4
\$\begingroup\$

Python 2, 38 bytes

a,b=input()
while b:print b%-~a;b/=a+1

Try it online!


outputs newline separated coefficients

Example output for 30, 3904800:

9
8
2
7
4

=> 9*x^0 + 8*x^1 + 2*x^2 + 7*x^3 + 4*x^4

\$\endgroup\$
3
\$\begingroup\$

VBA, 75 bytes

Sub f(b,n)
b=b+1
Do While n>0
s=n Mod b &" " &s
n=n\b
Loop
Debug.?s
End Sub

When it automatically formats, it looks like this:

Sub f(b, n)
    b = b + 1
    Do While n > 0
        s = n Mod b & " " & s
        n = n \ b
    Loop
    Debug.Print s
End Sub

The \ operator is a floor divide

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

AHK, 63 bytes

a=%1%
b=%2%
a+=1
While b>0
{s:=Mod(b,a) " "s
b:=b//a
}
Send,%s%

AutoHotkey assigns numbers 1-n as variable names for the incoming parameters. It causes some problems when you try to use those in functions because it thinks you mean the literal number 1 instead of the variable named 1. The best workaround I can find is to assign them to different variables.

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

Java, 53 bytes

a->b->{while(b>0){System.out.println(b%-~a);b/=a+1;}}

Outputs a list of coefficients. Thanks to ovs for the maths.

The expression must be assigned to a Function<Integer, IntConsumer> and called by first applying the function, then accepting the int. No imports are needed with Java 9's jshell:

C:\Users\daico>jshell
|  Welcome to JShell -- Version 9-ea
|  For an introduction type: /help intro

jshell> Function<Integer, IntConsumer> golf =
        a->b->{while(b>0){System.out.println(b%-~a);b/=a+1;}}
golf ==> $Lambda$14/13326370@4b9e13df

jshell> golf.apply(30).accept(3904800)
9
8
2
7
4
\$\endgroup\$
1
\$\begingroup\$

Common Lisp, 87 bytes

(defun p(x y)(multiple-value-bind(q m)(floor y (1+ x))(if(= 0 q)`(,m)`(,m ,@(p x q)))))

Ungolfed:

(defun find-polynomial (f<1> f<1+f<1>>)
  (multiple-value-bind (q m)
      (floor f<1+f<1>> (1+ f<1>))
    (if (zerop q) `(,m)
      (cons m (find-polynomial f<1> q)))))
\$\endgroup\$
0
\$\begingroup\$

C#, 62 bytes

(a,b)=>{var r="";a++;while(b>0){r+=(b%a)+" ";b/=a;}return r;};
\$\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.