Kleinste nullfreie Basis

28

Bei einer positiven Ganzzahl nwird die kleinste Basis ausgegeben, bei der b >= 2die Darstellung von nin base bohne führende Nullen kein a enthält 0. Dies können Sie b <= 256für alle Eingaben annehmen .

Testfälle

1 -> 2 (1)
2 -> 3 (2)
3 -> 2 (11)
4 -> 3 (11)
5 -> 3 (12)
6 -> 4 (12)
7 -> 2 (111)
10 -> 4 (22)
17 -> 3 (122)
20 -> 6 (32)
50 -> 3 (1212)
100 -> 6 (244)
777 -> 6 (3333)
999 -> 4 (33213)
1000 -> 6 (4344)
1179360 -> 23 ([12, 9, 21, 4, 4])
232792560 -> 23 ([15, 12, 2, 20, 3, 13, 1])
2329089562800 -> 31 ([20, 3, 18, 2, 24, 9, 20, 22, 2])
69720375229712477164533808935312303556800 -> 101 ([37, 17, 10, 60, 39, 32, 21, 87, 80, 71, 82, 14, 68, 99, 95, 4, 53, 44, 10, 72, 5])
8337245403447921335829504375888192675135162254454825924977726845769444687965016467695833282339504042669808000 -> 256 ([128, 153, 236, 224, 97, 21, 177, 119, 159, 45, 133, 161, 113, 172, 138, 130, 229, 183, 58, 35, 99, 184, 186, 197, 207, 20, 183, 191, 181, 250, 130, 153, 230, 61, 136, 142, 35, 54, 199, 213, 170, 214, 139, 202, 140, 3])
Mego
quelle
1
Was sind die Werte für zehn, elf usw. in höheren Basen, die Sie verwenden? Enthalten sie Nullen?
Stephen
19
@Stephen Die für die obigen Ziffern gewählten Werte 9spielen keine Rolle, da dies nicht der Fall ist 0.
Mego
9
Dies ist OEIS A106370 .
Ingenieur Toast
1
@Titus Das ist ein guter Punkt. Ich werde die Basis auf etwas Vernünftiges beschränken.
Mego
1
@Mego: Versuchen Sie es mit 232792560. Es ist der lcm von 2,3, ..., 20, also hat er in jeder Basis <= 20 eine 0 als niedrigstwertige Ziffer.
Nate Eldredge

Antworten:

15

Pyth , 6 Bytes

f*FjQT

Überprüfen Sie alle Testfälle.

Wie es funktioniert

f * FjQT ~ Volles Programm.

f ~ Erste positive ganze Zahl, bei der die Bedingung wahr ist.
   jQT ~ Die Eingabe, die in die Basis des aktuellen Elements konvertiert wurde.
 * F ~ Produkt. Wenn die Liste 0 enthält, ist sie 0, ansonsten ist sie streng positiv.
          0 -> Falsy; > 0 -> Wahrheit.
        ~ Das Ergebnis implizit ausgeben.

Obwohl Pyths fauf 1, 2, 3, 4, ...(beginnend mit 1) arbeitet, behandelt Pyth Zahlen in Basis 1 (unär) als eine Reihe von Nullen, sodass Basis 1 ignoriert wird.

Mr. Xcoder
quelle
Netter Missbrauch der Tatsache, dass Pyths Basis-1-Darstellung nur Nullen enthält.
Erik der Outgolfer
@EriktheOutgolfer Danke! Ich werde diesbezüglich eine Erklärung hinzufügen.
Mr. Xcoder
Pyth ist nicht die einzige Sprache, deren unäre Darstellung Nullen als Ziffern verwendet. Hinweis : P
Mego
Du hast geschrieben 0 -> Falsy; > 0 -> Truthy. Ist das eine Absicht, 0die sowohl Truthyals auch Falsyin dieser Situation ist?
Brian J
@BrianJ >Vor dem zweiten steht ein Zeichen 0, was bedeutet, dass alles, was höher als 0 ist, wahr ist.
Mr. Xcoder
11

C  52  50 Bytes

i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;return i;}

Probieren Sie es online!

C (gcc),  47-45  Bytes

i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;n=i;}

Probieren Sie es online!


Zwei Bytes gespart dank des Vorschlags von @ Nevay auf die Antwort von @ Kevin Cruijssen!

Steadybox
quelle
2
Die letztere Version funktioniert nur durch Zufall, auch wenn Sie auf einem bestimmten Compiler bestehen. Und natürlich ist keine der Versionen wirklich C.
AnT
3
@AnT es ist C .. es wird eine Menge Warnungen geben, aber es wird kompiliert. Solange Sie einen Compiler finden, der für Ihren Code funktioniert, geht es Ihnen gut
Felipe Nardi Batista
1
@Blacksilver k%iist hier ein Ternary -Check. Eine lesbare Variante wäre k=(k%i?k:n*++i);oder noch deutlicher: if(k%i){k=k;}else{k=n*++i;}.
Kevin Cruijssen
1
Sie können auch beide mit 2 Bytes Golf spielen: i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;return i;}und i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;n=i;}. Der gesamte Kredit geht an @Nevay , der diesen Vorschlag auf meiner portierten Java 8-Antwort gepostet hat .
Kevin Cruijssen
1
@Felipe Nardi Batista: Mir ist bewusst, dass in den CodeGolf-Regeln "solange es kompiliert" und so weiter steht. Allerdings ist die Tatsache , dass es „kompiliert“ nicht in irgendeiner Weise unter Beweis stellen , dass sie C. Dies ist nicht C. Typlos Erklärungen wie i, k;und f(n)in alten Versionen von C (K & R) existiert, aber nur in der Zeit, in returnrunden Klammern benötigt um seine Streit. Wenn Sie K & R mit verwenden möchten i,k;, müssen Sie auch verwenden return(i);. Die oben genannten möglicherweise Gnuc, aber nicht C.
AnT
8

Haskell , 56 52 48 Bytes

b#n=n<1||mod n b>0&&b#div n b
f n=until(#n)(+1)2

Probieren Sie es online!

Ziemlich einfach, aber es gibt keine guten Möglichkeiten, es zu verkürzen

EDIT: Danke an Laikoni für das Speichern von 4 Bytes! Ich weiß nicht, warum ich nie daran gedacht habe !!0. Ich hätte wahrscheinlich versuchen sollen, diese Klammern zu entfernen, aber ich habe vage Erinnerungen an einen seltsamen Fehler, wenn Sie versuchen, ||und &&zusammen zu verwenden. Vielleicht verwechsle ich es mit den Gleichstellungsoperatoren.

EDIT 2: Danke @Lynn für die Rasur weiterer 4 Bytes! Ich weiß nicht, wie ich es untilvorher noch nie gewusst habe .

user1472751
quelle
1
Sie haben mich mit fast genau der gleichen Lösung um eine Minute geschlagen. :) !!0ist kürzer als headund ich denke, Sie können die Klammer fallen lassen #.
Laikoni
2
Der kriminell unterschätzte until :: (a → Bool) → (a → a) → a → aspeichert vier Bytes:f n=until(#n)(+1)2
Lynn
6

Schale , 7 Bytes

→V▼MBtN

Probieren Sie es online!

Erläuterung

→V▼MBtN
     tN    list of natural numbers starting from 2
   MB      convert the (implicit) input to each of those bases
 V▼        find the (1-based) index of the first result where the minimum digit is truthy
→          add 1 to this index
Löwe
quelle
5

Python 2 , 57 Bytes

n=x=input()
b=2
while x:z=x%b<1;b+=z;x=[x/b,n][z]
print b

Probieren Sie es online!

Dies ist ein Byte kürzer als eine rekursive Funktion:

f=lambda n,b=1,x=1:b*(x<1)or f(n,b+(x%b<1),[x/b,n][x%b<1])
Lynn
quelle
1
Übrigens ist dies meiner Lösung ziemlich ähnlich.
Erik der Outgolfer
3

05AB1E , 6 Bytes

-4 Bytes dank Adnan

1µNвPĀ

Probieren Sie es online!

Okx
quelle
10 bytes: [¹NÌDŠвPĀ#
Neil
2
1µNвPĀ works for 6 bytes
Adnan
@Adnan I knew it was way too long
Okx
LB0.å0k is another method entirely >_>.
Magic Octopus Urn
3

Husk, 9 bytes

←foΠ`B⁰tN

Try it online!

Explanation

            -- input N
        tN  -- tail of [1..] == [2..]
←f(    )    -- filter with the following:
    `B⁰     --   convert N to that base
   Π        --   product (0 if it contains 0)
←           -- only keep first element
ბიმო
quelle
3

Java 8, 61 56 54 bytes

n->{int b=2,t=n;for(;t>0;)t=t%b++<1?n:t/--b;return b;}

Try it here.

Explanation:

n->{            // Method with integer as both parameter and return-type
  int b=2,      //  Base-integer, starting at 2
      t=n;      //  Temp-integer, copy of the input
  for(;t>0;)    //  Loop as long as `t` is not 0
    t=t%b++<1?  //   If `t` is divisible by the base `b`
                //   (and increase the base `b` by 1 afterwards with `b++`)
       n        //    Set `t` to the input `n`
      :         //   Else:
       t/--b;   //    Divide `t` by the `b-1`
                //    (by decreasing the base `b` by 1 first with `--b`)
                //  End of loop (implicit / single-line body)
  return b;     //  Return the resulting base
}               // End of method

I have the feeling this can be golfed by using an arithmetic approach. It indeed can, with a port of @Steadybox' C answer, and then golfed by 2 bytes thanks to @Nevay.

Old (61 bytes) answer:

n->{int b=1;for(;n.toString(n,++b).contains("0"););return b;}

Try it here.

Explanation:

n->{         // Method with Integer as both parameter and return-type
  int b=1;   //  Base-integer, starting at 1
  for(;n.toString(n,++b).contains("0"););
             //  Loop as long as the input in base-`b` does contain a 0,
             //  after we've first increased `b` by 1 before every iteration with `++b`
  return b;  //  Return the resulting base
}            // End of method
Kevin Cruijssen
quelle
2
54 bytes: n->{int b=2,t=n;for(;t>0;)t=t%b++<1?n:t/--b;return b;}
Nevay
2

Japt, 8 bytes

@ìX e}a2

Try it online!

Explanation

@    }a2

Return the first number (X) to pass the function, starting at 2

ìX

Convert the input number to an array of base-X digits.

e

Check if all digits are truthy.

Justin Mariner
quelle
Won't this fail if the array contains any multiple of 10?
Shaggy
@Shaggy My understanding was that, according to OPs comment, that the digits for bases above 9 don't count as zero.
Justin Mariner
Ah, I see that now. There's a problem with the phrasing of the challenge, so (or I'm just too tired!).
Shaggy
2

JavaScript (ES6), 43 41 37 bytes

n=>(g=x=>x?g(x%b++?x/--b|0:n):b)(b=1)

Test cases

Arnauld
quelle
2

Brachylog, 11 bytes

;.≜ḃ₎¬∋0∧1¬

Try it online!

Explanation

;.≜ḃ₎           The Input represented in base Output…
     ¬∋0        …contains no 0
        ∧1¬     And Output ≠ 1
Fatalize
quelle
2

Python 2, 57 bytes

n=m=input()
b=2
while m:c=m%b<1;b+=c;m=(m/b,n)[c]
print b

Try it online!

-1 thanks to Felipe Nardi Batista.
-2 thanks to Lynn (and now this is a dupe of her solution :D)

Erik the Outgolfer
quelle
59 bytes by changing a,b=a+c,d to a+=c;b=d
Felipe Nardi Batista
I think you can replace while m>1 by while m (and then we’re tied!)
Lynn
@Lynn That's why I commented on your solution, it would be exactly the same then.
Erik the Outgolfer
1
@Lynn I already knew :p otherwise I'd have asked you to delete yours.
Erik the Outgolfer
2

APL (Dyalog), 20 19 bytes

1+⍣{~0∊⍺⊥⍣¯1n}≢n←⎕

Try it online!

As usual, thanks to @Adám for helping out in chat and getting the code to work in TIO. Also, saving 1 byte.

This is tradfn (traditional function) body. To use it, you need to assign it a name (which is in TIO's header field), enclose it in s (one before the name and one in TIO's footer field), and then call it using its name. Since it uses a quad () to take the user's input, it's called as f \n input instead of the usual f input

How?

1+⍣{~0∊⍺⊥⍣¯1n}≢n←⎕   Main function.
                  n←⎕  Assigns the input to the variable n
1+⍣{           }≢      Starting with 1, add 1 until the expression in braces is truthy
    ~0                returns falsy if 0 "is in"
                      convert
            n         the input
         ⍣¯1           to base
                      left argument (which starts at 1 and increments by 1)

The function then returns the resulting base.

J. Sallé
quelle
1
Golfing tip: since n←⎕ will be a simple number and you need 1 as initial argument to the rest of the code, you can just count the number of elements in n (which is 1), by replacing 1⊣ with . Try it online!
Adám
1

Proton, 40 bytes

x=>filter(y=>all(digits(y,x)),2..x+3)[0]

Try it online!

HyperNeutrino
quelle
1
This is invalid. 2..x checks for bases in the interval [2, x), hence it fails for test cases 1 and 2.
Mr. Xcoder
1

R, 79 71 66 63 65 bytes

function(n){while(!{T=T+1;all(n%/%T^(0:floor(log(n,T)))%%T)})T
T}

Try it online!

This answer is based on Giuseppe's re-arrangement in one single loop.

Saved 8 bytes thanks to JDL, and 6 bytes thanks to Giuseppe.

NofP
quelle
1
You can sub b for T, which starts out defined as TRUE == 1, removing the need for b=1. Similarly you can sub F for k (F is FALSE)
JDL
I see what you did there. That's a useful one to know!
NofP
1
66 bytes using m%/%T (integer division) instead of (m-m%%T)/T
Giuseppe
65 bytes. it was a bit messy but I suspected getting rid of the nested loops would save something; I just thought it would be more than 1 byte :(
Giuseppe
1

MATL, 13 12 bytes

`G@Q_YAA~}@Q

Try it online!

-1 byte thanks to Luis Mendo. This program does not handle testcases bigger than 2^53 (flintmax, the maximum consecutive integer representable by a floating point type), as the default datatype is double in MATL. However, it should be able to find any arbitrary zeroless base below that number.

`            % Do while
 G           %  Push input
  @ _        %  Outputs the iteration number, negate.
     YA      %  Convert input to base given by the iteration number, the negative number is to instruct MATL we want an arbitrary high base with a integer vector rather than the default character vector we know from hexadecimal
       A~    %  If they're not all ones, repeat
         }   % But if they are equal, we finally
          @  %  Push the last base
   Q       Q %  As base 1 makes no sense, to prevent MATL from errors we always increase the iteration number by one.
Sanchises
quelle
@LuisMendo I should really start reading the docs better. Thanks.
Sanchises
This doesn't seem to work for the larger test cases, but I don't know enough about MATL/Matlab to know if that's caused by integer limits or not.
Mego
@Mego I tested my 13 byte version which should be equivalent to the current version up to 1e6, on MATLAB R2017a. What test setup resulted in problems for you?
Sanchises
The last 2 test cases cause errors.
Mego
@Mego Ah I didn't see those testcases before. This is due to the implementation of MATLs YA using doubles internally, so it can only handle inputs up to the maximum consecutive integer representable by a double (see flintmax). Does this invalidate the answer? In principle the algorithm works for arbitrary base, I've explicitly worked around another command that would only do up to base 36.
Sanchises
0

PHP, 59+1 bytes

using builtins, max base 36:

for($b=1;strpos(_.base_convert($argn,10,++$b),48););echo$b;

no builtins, 6360+1 bytes, any base:

for($n=$b=1;$n&&++$b;)for($n=$argn;$n%$b;$n=$n/$b|0);echo$b;

Run as pipe with -nR or try them online.

Titus
quelle
0

J, 26 bytes

]>:@]^:(0 e.]#.inv[)^:_ 2:

Would love to know if this can be improved.

The main verb is a the dyadic phrase:

>:@]^:(0 e.]#.inv[)^:_

which is given the input on the left and the constant 2 on the right. That main verb phrase then uses J's Do..While construct, incrementing the right y argument as long as 0 is an element of e. the original argument in base y.

Try it online!

Jonah
quelle
0

Lua, 77 76 bytes

b=2n=...N=n
while~~N>0 do
if N%b<1then
b=b+1N=n
else
N=N//b
end
end
print(b)

Try it online!

Felipe Nardi Batista
quelle
0

Milky Way, 38 bytes

^^'%{255£2+>:>R&{~^?{_>:<;m_+¡}}^^^}

usage: ./mw base.mwg -i 3


Explanation

code                                 explanation                    stack layout

^^                                   clear the preinitialized stack []
  '                                  push the input                 [input]
   %{                              } for loop
     255£                             push next value from 0..254   [input, base-2]
         2+                           add 2 to the get the base     [input, base]
           >                          rotate stack right            [base, input]
            :                         duplicate ToS                 [base, input, input]
             >                        rotate stack right            [input, base, input]
              R                       push 1                        [input, base, input, 1]
               &{~             }      while ToS (=remainder) is true ...
                  ^                    pop ToS                      [input, base, number]
                   ?{         }        if ToS (=quotient) ...
                     _>:<;              modify stack                [input, base, number, base]
                           m            divmod                      [input, base, quotient, remainder]
                           _+¡         else: output ToS (0) + SoS and exit
                                ^^^   pop everything but the input.

I'm sure this can be shortened using a while-loop instead of a for loop, but I couldn't get it to work.

ovs
quelle
0

Stacked, 23 bytes

{!2[1+][n\tb all]until}

Try it online!

This increments ([1+]) J starting from two (2) while the baseJ representation of the input has no zeroes (all and until).

Conor O'Brien
quelle