Самая маленькая нулевая база

28

Учитывая положительное целое число n, выведите наименьшую базу, в b >= 2которой представление nв базе bбез начальных нулей не содержит a 0. Вы можете предположить, чтоb <= 256 для всех входов.

Тестовые случаи

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
источник
1
Какие значения для десяти, одиннадцати и т. Д. В высших базах вы используете? Они содержат нули?
Стивен
19
@Stephen Значения, выбранные для цифр выше, 9не имеют значения, потому что они не имеют значения 0.
Мего
9
Это OEIS A106370 .
Тост инженера
1
@ Titus Это хороший момент. Я ограничу базу чем-то разумным.
Mego
1
@Mego: Попробуйте 232792560. Это lcm 2,3, ..., 20, поэтому в каждой базе <= 20 он имеет 0 как наименее значащая цифра.
Нейт

Ответы:

15

Pyth , 6 байт

f*FjQT

Проверьте все контрольные примеры.

Как это работает

f * FjQT ~ Полная программа.

f ~ Первое положительное целое число, если условие истинно.
   jQT ~ Ввод преобразуется в базу текущего элемента.
 * F ~ Продукт. Если список содержит 0, то это 0, иначе он строго положительный.
          0 -> Ложь; > 0 -> Правда.
        ~ Вывести результат неявно.

Хотя Pyth fработает 1, 2, 3, 4, ...(начиная с 1), Pyth рассматривает числа в базе 1 (унарные) как группу нулей, поэтому база 1 игнорируется.

Мистер Xcoder
источник
Хорошее злоупотребление тем фактом, что представление Пайта в base-1 - все нули.
Эрик Outgolfer
@EriktheOutgolfer Спасибо! Я добавлю объяснение по этому поводу.
г-н Xcoder
Pyth - не единственный язык, унарное представление которого использует нули в качестве намеков на цифры : P
Mego
Вы написали 0 -> Falsy; > 0 -> Truthy. Это преднамеренное, что 0и то, Truthyи другое Falsyв этой ситуации?
Брайан Д.
@BrianJ Перед вторым есть >знак 0, который означает, что все, что выше 0, является правдой.
г-н Xcoder
11

C,  52  50 байтов

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

Попробуйте онлайн!

C (gcc),  47  45 байтов

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

Попробуйте онлайн!


Два байта сохранены благодаря предложению @ Nevay по ответу @Kevin Cruijssen!

Steadybox
источник
2
Последняя версия работает только по случайности, даже если вы настаиваете на конкретном компиляторе. И, конечно же, ни одна из версий на самом деле не является C.
AnT
3
@ Это C .. он выдаст много предупреждений, но скомпилирует. пока вы найдете компилятор, который работает для вашего кода, у вас все в порядке
Фелипе Нарди Батиста,
1
@ Blacksilver k%i- это троичная проверка здесь. Более читаемый вариант был бы k=(k%i?k:n*++i);или даже более понятен if(k%i){k=k;}else{k=n*++i;}.
Кевин Круйссен,
1
Также вы можете играть в гольф как по 2 байта: так i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;return i;}и i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;n=i;}. Вся заслуга принадлежит @Nevay, который разместил это предложение в моем портированном ответе на Java 8 .
Кевин Круйссен,
1
@Felipe Nardi Batista: Мне известно о том, что правила CodeGolf гласят «пока он компилируется» и так далее. Однако тот факт, что он «компилируется», никоим образом не доказывает, что это C. Это не C. Декларации без типов, подобные i, k;и f(n)существовавшие в древних версиях C (K & R), но только в эпоху, когда returnтребовались круглые скобки вокруг аргумент. Если вы хотите использовать K & R с i,k;, вы также должны использовать return(i);. Выше может быть gnuc, но не C.
AnT
8

Haskell , 56 52 48 байт

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

Попробуйте онлайн!

Довольно простой, но не может придумать хороших способов сократить его

РЕДАКТИРОВАТЬ: Спасибо Laikoni за спасение мне 4 байта! Не знаю, почему я никогда не думал о !!0. Я, вероятно, должен был попытаться удалить эти скобки, но у меня есть смутные воспоминания о какой-то странной ошибке, когда вы пытаетесь использовать ||и &&вместе. Может быть, я путаю это с операторами равенства.

РЕДАКТИРОВАТЬ 2: Спасибо @Lynn за бритье еще 4 байта! Не знаю, как я никогда untilраньше не знал .

user1472751
источник
1
Вы избили меня на минуту с почти точно таким же решением. :) !!0короче, headи я думаю, вы можете опустить скобки #.
Лайкони
2
Преступный недооцененный until :: (a → Bool) → (a → a) → a → aэкономит четыре байта:f n=until(#n)(+1)2
Линн
6

Шелуха , 7 байт

→V▼MBtN

Попробуйте онлайн!

объяснение

→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
Лео
источник
5

Python 2 , 57 байт

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

Попробуйте онлайн!

Это на один байт короче рекурсивной функции:

f=lambda n,b=1,x=1:b*(x<1)or f(n,b+(x%b<1),[x/b,n][x%b<1])
Линн
источник
1
Кстати, это очень похоже на мое решение.
Эрик Outgolfer
3

05AB1E , 6 байтов

-4 байта благодаря Аднану

1µNвPĀ

Попробуйте онлайн!

Okx
источник
10 байтов:[¹NÌDŠвPĀ#
Нил
2
1µNвPĀработает на 6 байтов
Аднан
@Adnan Я знал, что это было слишком долго
Okx
LB0.å0kэто еще один метод полностью> _>.
Волшебная урна осьминога
3

Java 8, 61 56 54 байта

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

Попробуй это здесь.

Объяснение:

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

У меня такое чувство, что это можно сделать с помощью арифметического подхода. Это действительно может, с портом ответа @Steadybox 'C , а затем игра в гольф на 2 байта благодаря @Nevay .

Старый ( 61 байт ) ответ:

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

Попробуй это здесь.

Объяснение:

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
Кевин Круйссен
источник
2
54 байта:n->{int b=2,t=n;for(;t>0;)t=t%b++<1?n:t/--b;return b;}
Невай
2

Japt , 8 байт

@ìX e}a2

Попробуйте онлайн!

объяснение

@    }a2

Вернуть первое число ( X) для прохождения функции, начиная с2

ìX

Преобразуйте входной номер в массив базовых Xцифр.

e

Проверьте правильность всех цифр.

Джастин Маринер
источник
Разве это не сработает, если массив содержит несколько кратных 10?
Лохматый
@ Shaggy Насколько я понимаю, согласно комментариям OP, цифры для баз выше 9 не считаются нулями.
Джастин Маринер
Ах, я вижу это сейчас. Есть проблема с формулировкой задачи, поэтому (или я просто слишком устал!).
Лохматый
2

JavaScript (ES6), 43 41 37 байт

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

Контрольные примеры

Arnauld
источник
2

Python 2 , 57 байт

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

Попробуйте онлайн!

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

Erik the Outgolfer
источник
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é
источник
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
источник
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
источник
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
источник
@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
источник
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
источник
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
источник
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
источник