Digit small numbers

A digit small number is a positive integer $$\n\$$ such for any two numbers that multiply to $$\n\$$, their total number of digits is more than the digits in $$\n\$$.

In otherwords: there are no two positive integers $$\a\$$ and $$\b\$$ such that:

$$\ ab = n \$$

and

$$\ \left\lfloor\log_{10}(a)\right\rfloor+\left\lfloor\log_{10}(b)\right\rfloor <\left\lfloor\log_{10}(n)\right\rfloor \$$

For example 363 is digit small. It can be made as the product of two numbers 3 ways

$$\ 1\times363=363\\ 3\times121=363\\ 11\times33=363\\ \$$

Each time we have 4 digits on the left hand side and 3 on the right hand side.

As another example 48 is not digit small because we can write it as

$$\ 6\times8=48 \$$

where each side of the equation has 2 digits in total.

Given a positive number output one of two distinct values depending on whether the input was digit small. For example you could output 1 when the input is digit small and 0 if it is not, or True and False etc.

This is so answers will be scored in bytes.

Test cases

Here are the first 25 digit small numbers:

1,2,3,4,5,6,7,8,9,11,13,17,19,22,23,26,29,31,33,34,37,38,39,41,43

Hint

If you drop the test cases into OEIS you will get A122427. This sequence is useful, but you will have to prove where it is the same, or find the cases in which it is different.

• How big numbers do we have to handle?
Nov 15 '21 at 11:22
• Do the output values have to be consistent? Nov 15 '21 at 12:06
• @cairdcoinheringaahing Yes. Nov 15 '21 at 12:07

05AB1E, 5 bytes

Using the hint, suggested by Kevin Cruijssen

Ñ§{θQ

Try it online!

Cast the divisors Ñ to string §, sort {, is the last one θ equal to the input Q?

Or 9 bytes without the hint, -1 byte thanks to Kevin Cruijssen:

ÑÂøεS∍‹}P

Try it online!

Ñ           # divisors of the input
Âø         # zip with its reverse
ε   }    # map over the divisor pairs
S       #   split into a single list of digits
∍      #   extend the input to that length
‹     #   is the input less than the extended version?
P   # product / boolean all
• 9 bytes: ÑÂøεS∍‹}P (outputting 1 for digit small numbers, 0 for others) Nov 15 '21 at 13:31
• 5 bytes using the hint: Ñ§{θQ (also outputs 1 for digit small numbers, 0 for others) Nov 15 '21 at 13:51
• I don't think this is 5 bytes? § and θ aren't in ASCII, certainly, and I don't know of any common character encoding which (1) contains all these characters and (2) contains less than 256 characters total. Nov 17 '21 at 21:56
• @rationalis 05AB1E has its own codepage which contains all these characters. Though you're right, this is not a very common encoding ;)
– ovs
Nov 17 '21 at 22:36

Pari/GP, 29 bytes

n->!sumdiv(n,d,Str(d)>Str(n))

Try it online!

Using the hint.

Let $$\\#n\$$ denote the number of digits in $$\n\$$. Then $$\n\$$ has a divisor $$\d\$$ that is lexicographically greater than $$\n\$$ $$\\iff\$$ $$\d * 10^{\#n-\#d} > n\$$ $$\\iff\$$ $$\n/d < 10^{\#n-\#d}\$$ $$\\iff\$$ $$\\#(n/d) \le \#n - \#d\$$ $$\\iff\$$ $$\n\$$ is not digit small.

• Nice proof of the hint!
– Lynn
Nov 16 '21 at 18:16

Python 2, 44 bytes

lambda n:any(i>n>n%i<1for i in range(n))

Try it online!

Outputs True/False negated. Looks for an i that's a divisor of n and is lexicographically smaller than n. The two conditions are combined into an inequality chain, connected by Python 2's willingness to compare strings and numbers (strings are bigger).

This chain also benefits from short-circuiting. Checking i=0 would trigger an error when we check n%i, but since 0 is never lexicographically above n, the first condition always fails and the second one is never reached.

R, 454039 38 bytes

Or R>=4.1, 31 bytes by replacing the word function with \.

function(n,k=1:n)any(c("",k[!n%%k])>n)

Try it online!

Using the hint (proof in @alephalpha's answer).

Outputs FALSE for digit small number and TRUE otherwise.

Converts list of divisors k[!n%%k] to character by prepending empty string. Then compares the vector with n (casted implicitly to character); "">n is always FALSE.

Without the hint:

R, 55 bytes

Or R>=4.1, 48 bytes by replacing the word function with \.

function(n,k=1:n,d=k[!n%%k],-=nchar)all(-d+-(n/d)>-n)

Try it online!

Vyxal, 1611 10 bytes

KḂZƛṅL;?Lc

Try it Online!

Hmm yes Jelly 05AB1E porting goes brr. Outputs 0 for digit small, 1 for everything else.

Explained

KḂZƛṅL;?Lc
K            # factors_of(input)
Ḃ           # that, and that reversed
Z          # zip those two -> pairs of factors that have product = input
ƛṅL;      # join each on spaces and take lengths
?L    # input length
c   # is in that list?

MathGolf, 12 7 bytes

─░s┤l¡Þ

Outputs 1 if it's a digit small number, -1 if not.

Try it online.

Almost halved the byte-count by using the hint.

Original 12 bytes answer without using the hint:

─_x^mÆy£l£>╓

Outputs 1 if it's a digit small number, 0 if not.

Try it online.

Explanation:

─           # Get a list of divisors from the (implicit) input-integer
░          # Convert each integer to a string
s         # Sort this list of strings lexographically
┤        # Pop the last item (unfortunately without popping the remainder-list)
l       # Push the input as string
=      # Check that it's equal to this integer
# (if not, it implicitly indices since it's a string, resulting in -1)
Þ     # Discard everything from the stack except the top (to get rid of the
# remainder-list)
# (after which the entire stack is output implicitly as result)

─           # Get a list of divisors from the (implicit) input-integer
_          # Duplicate this list
x         # Reverse the copy
^        # Zip the two lists together, creating pairs
m       # Map over these strings,
Æ      # using five characters as inner codeblock:
y     #  Join the pair together to a string
£    #  Pop and push its length
l£  #  Push the length of the input (as string) as well
> #  Check if the length is larger than the input-length
╓       # After the map: pop and push its minimum to check if any were falsey
# (after which the entire stack is output implicitly as result)

JavaScript (ES6), 45 bytes

Expects $$\n\$$ as a string. Works in theory up to $$\n=99999999999\$$ (although the call stack will overflow way before that).

f=(n,k)=>k>n||!n[(k+[n/k]).length-1]&f(n,-~k)

Try it online!

JavaScript (ES6),  35  33 bytes

Using alephalpha's method is significantly shorter.

Expects $$\n\$$ as a string. Returns $$\0\$$ for true or $$\1\$$ for false.

f=(n,k)=>k>n?0:[k]>n>n%k|f(n,-~k)

Try it online!

• This challenge feels like the perfect oppurtunity to use JS's default sort. Oh well, another time. Nov 18 '21 at 8:08

Retina, 52 bytes

.+
*
Lv$(_+)$(?<=^(\1)+)
$.=,$.1$#2 +.,. , A\d ^$

Try it online! Link includes test cases. Explanation:

.+
*

Convert to unary.

Lv$(_+)$(?<=^(\1)+)

For each pair of factors of the input...

$.=,$.1$#2 ... convert the input back to decimal and append the two factors. +.,. , For each pair of factors, check whether this is a digit small factorisation. A\d Delete all factorisations that were digit small. ^$

Check that there are no factorisations left.

APL+WIN, 49 40 bytes

Prompts for integer. 1 = true, 0 = false.

×/(+/⍴¨⍕¨v,n÷v←↑⌽(0=m|n)/m←⍳⌊n*.5)>⍴⍕n←⎕

Try it online!

Jelly, 7 6 bytes

ÆDDṀḌ=

Try it online!

-7 bytes (50%!) thanks to Kevin Cruijssen!
-1 byte thanks to ovs!

• 7 bytes using the hint. I'm not too skilled with Jelly, so can probably be a byte shorter. Nov 15 '21 at 16:21
• @KevinCruijssen Very nice, I knew the hint had to be useful! I can't spot any obvious golfs at the moment, but I'll take a proper look when not on mobile :) Nov 15 '21 at 17:35
• saves a byte over ṢṪ: tio.run/##y0rNyan8//9wm4vLw50ND3f02P4/3H6s/f9/ExMA
– ovs
Nov 16 '21 at 8:37
• @ovs Nice catch, thanks! Nov 16 '21 at 8:46

TI-Basic, 40 bytes

Input N
max(1,seq(Inot(fPart(N/I)),I,1,N
min(int(log(Ans))+int(log(N/Ans))≥int(log(N

Output is stored in Ans and displayed. Outputs 1 for digit small numbers and 0 for others.

Charcoal, 21 bytes

Ｎθ⬤…·¹θ∨﹪θι‹Ｌθ⁺ＬιＬ÷θι

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for digit small, nothing if not. Explanation:

Ｎθ                      Input n as a number
…·¹θ                 Inclusive range from 1 to n
⬤                     All values satisfy
ι             Current value
﹪               Does not divide
θ              Input n
∨                Logical Or
θ          Input value
Ｌ           Length
‹            Is less than
ι       Current value
Ｌ        Length
⁺         Plus
θ    Input n
÷     Integer divide
ι   Current value
Ｌ      Length
Implicitly print

Lua 5.1, 60 bytes

n=...for x=1,n do c=c or n%x<1 and#(x..n/x)<=#n end print(c)

Takes a number from command line arguments, prints false if the number fits the definition, otherwise prints true.

The algorithm simply checks if there is any number a up to n that is a factor of n and whose string concatenation with b=n/x is longer than string n; if yes, switch the output to true (does not fit the definition).

Excel, 73 bytes

=LET(a,SEQUENCE(A1^0.5),b,FILTER(a,MOD(A1,a)=0),MIN(LEN(b&A1/b))>LEN(A1))

Works for n < 1,099,513,724,929 = (2^20 + 1) ^ 2. You could get it down to 69 bytes by removing ^0.5; but it would only work for n <= 2^20.

• Generally golfing trumps size constraints. For example, default variable declarations in C are fine: n (defaulting to int x) is best for golfing even thought it constrains size to $32$-bit where long n is $64$-bit. Nov 16 '21 at 10:33

C (gcc), 77 $$\\cdots\$$ 74 70 bytes

r;d;s(n){n=log10(n);}f(n){for(r=d=1;++d<n;)r&=n%d||s(d)-~s(n/d)>s(n);}

Try it online!

Saved 2 bytes thanks to AZTECCO!!!
Saved 4 bytes thanks to upkajdt!!!

Inputs positive integer $$\n\$$.
Returns $$\1\$$ if $$\n\$$ is a digit small number or $$\0\$$ otherwise.

• 74 Bytes by removing ternary operator and removing +1 to log10() Nov 15 '21 at 13:25
• @AZTECCO Ah, nice stuff - change the x+2>y+1 to just x+1>y and use logical or on the divisibility - thanks! :D Nov 15 '21 at 13:36

Python 2, 54 bytes

f=lambda n:max(xfor x in range(1,n+1)if n%x==0)==n

Try it online!

• <1 instead of ==0 since the modulo can't be negative, and you can remove your +1 to convert the other == to a <. Nov 15 '21 at 20:46

Ruby, 42 bytes

->n{(1..n).all?{|x|n%x>0||x.to_s<=n.to_s}}

Try it online!

Japt, 7 bytes

¥â ñs Ì

Try it

• port of @Kevin Cruijssen answer.
¥       - input equal?
Ì  - last element of
â       - divisors of input
ñs    - sorted lexicographically

Zsh, 118 94 bytes

for i ({1..$1})(($1%i))||a+=($i);for e ($a)for f ($a)[[$#e+$#f -le$#1 && e*f -eq \$1 ]]&&<<<0

Attempt This Online!

Thanks to @pxeger for saving 24 bytes!

My first Zsh answer, uses the obvious solution. Outputs 0s if the number is not digit-small, nothing if it is. 99% sure there exists a shorter solution.

Burlesque, 10 bytes

Jfcqb0>m==

Try it online!

J      # Duplicate input
fc     # Factors
qb0>m  # Maximum lexicographically
==     # are Equal

Burlesque, 26 bytes

PppPfcJ<-z[m{imlnpPln.>}r&

Try it online!

Pp      # Push input to store
pP      # Retrieve input
fc      # Factors (of input)
J       # Duplicate factors
<-z[    # Zip list of factors with reversed list of factors
m{      # Map (for each pair of factors)
im    # Concat factors
ln    # Total number of digits
pPln  # Digits in input
.>    # Greater than (that of factors)
}
r&      # For all factors

Desmos, 146164 89 bytes

Had to add 18 bytes because the previous version only supported numbers up to 10000. Now it should support up to numbers around $$\10^{10}\$$. Thanks @fireflame241 for helping me with this change.

EDIT: Turns out, the change mentioned above actually allowed me to essentially halve the number of bytes in my code...

$$\f(n)\$$ returns 0 if $$\n\$$ is a digit small number, 1 if it is not.

a=[1...sqrtn]
b=a[mod(n,a)=0]
g(l)=floor(logl)
f(n)=\sign(\total(\{g(b)+g(n/b)<g(n),0\}))

Try It On Desmos!

Try It On Desmos! - Prettified

Probably not the best way to do it, but for now I think it is good enough. Uses the formula given in the problem.