10
\$\begingroup\$

Given a value x find the smallest numerical value greater than y that is capable of being multiplied and divided by x while retaining all original digits.

  • The new numbers do not lose digits.
  • The new numbers do not gain digits.

For example:

Input: x = 2, y = 250000

  • Original: 285714
    • Division: 142857
    • Multiplication: 571428

This is true because 285714 is greater than y; then when divided by x results in 142857 and when multiplied by x results in 571428. In both tests all of the original digits from 285714 are present and no extra digits have been added.


The Rules

  • X should be 2 or 3 as anything higher takes too long to calculate.
  • Y is required to be a whole number greater than zero.
  • The shortest code wins.

Test Cases

These are my most common test cases as they are the quickest to test for.

  • x = 2, y = 250000 = 285714
  • x = 2, y = 290000 = 2589714
  • x = 2, y = 3000000 = 20978514
  • x = 3, y = 31000000 = 31046895
  • x = 3, y = 290000000 = 301046895

Clarifications

  • The type of division doesn't matter. If you can get 2.05, 0.25, and 5.20 somehow then feel free.

Good luck to you all!

\$\endgroup\$
  • 4
    \$\begingroup\$ "X has to be a value between 2 and 5." - if X>=4, the number multiplied by X will be at least 16 times larger than the number divided by X, so surely it will have more digits \$\endgroup\$ – ngn Sep 27 '18 at 23:25
  • 2
    \$\begingroup\$ x can't be anything other than 2 or 3 since the product is x^2 times the quotient and both should have same number of digits. x = 1 will be a trivial case. IMO, there's no solution for x = 3 for any y though I might be wrong. \$\endgroup\$ – Jatin Sanghvi Sep 27 '18 at 23:27
  • 2
    \$\begingroup\$ Is division float or integer division? \$\endgroup\$ – Erik the Outgolfer Sep 28 '18 at 9:21
  • 3
    \$\begingroup\$ Test cases would be great \$\endgroup\$ – Stephen Sep 28 '18 at 13:00
  • 3
    \$\begingroup\$ I suspect I'm not the only person who is refraining from voting to reopen because the clarification actually makes the challenge more ambiguous, because the correct answer could change dependently on whether floating point output is considered or not. I suspect @EriktheOutgolfer 's question was not asking about allowing floating point output, but about whether it's permitted to use truncating integer division. (And I'm sorry if my comments added to the confusion.) \$\endgroup\$ – Ørjan Johansen Sep 29 '18 at 19:43

13 Answers 13

4
\$\begingroup\$

Husk, 14 bytes

ḟ§¤=OoDd§¤+d*/

Try it online!

Explanation

ḟ§¤=O(Dd)§¤+d*/  -- example inputs: x=2  y=1
ḟ                -- find first value greater than y where the following is true (example on 285714)
 §               -- | fork
         §       -- | | fork
              /  -- | | | divide by x: 142857
                 -- | | and
             *   -- | | | multiply by y: 571428
                 -- | | then do the following with 142857 and 571428
                 -- | | | concatenate but first take
           +     -- | | | | digits: [1,4,2,8,5,7] [5,7,1,4,2,8]
          ¤ d    -- | | | : [1,4,2,8,5,7,5,7,1,4,2,8]
                 -- | and
       d         -- | | digits: [2,8,5,7,1,4]
      D          -- | | double: [2,8,5,7,1,4,2,8,5,7,1,4]
                 -- | then do the following with [2,8,5,7,1,4,2,8,5,7,1,4] and [1,4,2,8,5,7,5,7,1,4,2,8]
   =             -- | | are they equal
  ¤ O            -- | | | when sorted: [1,1,2,2,4,4,5,5,7,7,8,8] [1,1,2,2,4,4,5,5,7,7,8,8]
                 -- | : truthy
                 -- : 285714
\$\endgroup\$
  • \$\begingroup\$ I adjusted the value for y to get a closer starting point and the result was incorrect for x = 3, y = 25000000. \$\endgroup\$ – PerpetualJ Sep 27 '18 at 21:28
  • \$\begingroup\$ @PerpetualJ: If you know the result then you can simply adjust y, and this version should be slightly faster (only the type-checking though). \$\endgroup\$ – ბიმო Sep 27 '18 at 21:30
  • \$\begingroup\$ I've adjusted it after some thought and edited my first comment. \$\endgroup\$ – PerpetualJ Sep 27 '18 at 21:32
  • \$\begingroup\$ @PerpetualJ: I've fixed it: made an assumption about - which was wrong. \$\endgroup\$ – ბიმო Sep 27 '18 at 21:45
  • 1
    \$\begingroup\$ @PerpetualJ: I wrote the program ;) I added an explanation, now everybody should understand what's going on. \$\endgroup\$ – ბიმო Sep 27 '18 at 21:59
5
\$\begingroup\$

Brachylog v2, 15 bytes

t<.g,?kA/p.∧A×p

Try it online!

Takes input in the form [x,y].

Explanation

t<.g,?kA/p.∧A×p
t                  Tail (extract y from the input)
 <                 Brute-force search for a number > y, such that:
  .                  it's the output to the user (called ".");
   g                 forming it into a list,
    ,?               appending both inputs (to form [.,x,y]),
      k              and removing the last (to form [.,x])
       A             gives a value called A, such that:
        /              first ÷ second element of {A}
         p             is a permutation of
          .            .
           ∧         and
            A×         first × second element of {A}
              p        is a permutation of {.}

Commentary

Brachylog's weakness at reusing multiple values multiple times shows up here; this program is almost all plumbing and very little algorithm.

As such, it might seem more convenient to simply hardcode the value of y (there's a comment on this question hypothesising that 2 is the only possible value). However, there are in fact solutions for y=3, meaning that unfortunately, the plumbing has to handle the value of y as well. The smallest that I'm aware of is the following:

                         315789473684210526
315789473684210526 × 3 = 947368421052631578
315789473684210526 ÷ 3 = 105263157894736842

(The technique I used to find this number isn't fully general, so it's possible that there's a smaller solution using some other approach.)

You're unlikely to verify that with this program, though. Brachylog's p is written in a very general way that doesn't have optimisations for special cases (such as the case where both the input and output are already known, meaning that you can do the verification in O(n log n) via sorting, rather than the O(n!) for the brute-force approach that I suspect it's using). As a consequence, it takes a very long time to verify that 105263157894736842 is a permutation of 315789473684210526 (I've been leaving it running for several minutes now with no obvious progress).

(EDIT: I checked the Brachylog source for the reason. It turns out that if you use p on two known integers, the algorithm used generates all possible permutations of the integer in question until it finds one that's equal to the output integer, as the algorithm is "input → indigits, permute indigits → outdigits, outdigits → output". A more efficient algorithm would be to set up the outdigits/output relationship first, so that the backtracking within the permutation could take into account which digits were available.)

\$\endgroup\$
  • \$\begingroup\$ Using a fork can decrease your code by 1 byte. Try it online! \$\endgroup\$ – Kroppeb Sep 28 '18 at 9:20
  • \$\begingroup\$ Also according to the docs, it seems checking if two known lists are a permutation is O(n²) swi-prolog.org/pldoc/man?predicate=permutation/2 \$\endgroup\$ – Kroppeb Sep 28 '18 at 9:24
  • \$\begingroup\$ @Kroppeb: the problem is that Brachylog's p doesn't run permutation/2 with two known lists, even when given two known integers as arguments; it generates all the permutations of the first integer (using permutation/2 with one known list) and then compares them against the second integer. \$\endgroup\$ – ais523 Nov 6 '18 at 14:54
4
\$\begingroup\$

Perl 6, 56 54 bytes

->\x,\y{(y+1...{[eqv] map *.comb.Bag,$_,$_*x,$_/x})+y}

Try it online!

Interesting alternative, computing n*xk for k=-1,0,1:

->\x,\y{first {[eqv] map ($_*x***).comb.Bag,^3-1},y^..*}
\$\endgroup\$
3
\$\begingroup\$

Clean, 92 bytes

import StdEnv
$n m=hd[i\\i<-[m..],[_]<-[removeDup[sort[c\\c<-:toString j]\\j<-[i,i/n,i*n]]]]

Try it online!

Pretty simple. Explanation coming in a while.

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

q, 65 bytes

{f:{asc 10 vs x};while[not((f y)~f y*x)&(f y*x)~f"i"$y%x;y+:1];y}

Split number on base 10, sort each ascending, and check if equal. If not, increment y and go again

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

JavaScript (ES6), 76 73 69 bytes

Saved 3 bytes by using eval(), as suggested by @ShieruAsakoto

Takes input as (x)(y).

x=>y=>eval("for(;(g=x=>r=[...x+''].sort())(y*x)+g(y/x)!=g(y)+r;)++y")

Try it online!

A recursive version would be 62 bytes, but it's not well suited here because of the high number of required iterations.

How?

The helper function \$g\$ takes an integer as input, converts it to an array of digit characters and sorts this array.

Example:

g(285714) = [ '1', '2', '4', '5', '7', '8' ]

To compare the digits of \$y\times x\$ and those of \$y/x\$ against those of \$y\$, we test whether the concatenation of \$g(y\times x)\$ with \$g(y/x)\$ is equal to the concatenation of \$g(y)\$ with itself.

When adding two arrays together, each of them is implicitly coerced to a comma-separated string. The last digit of the first array is going to be directly concatenated with the first digit of the second array with no comma between them, which makes this format unambiguous.

Example:

g(123) + g(456) = [ '1', '2', '3' ] + [ '4', '5', '6' ] = '1,2,34,5,6'

But:

g(1234) + g(56) = [ '1', '2', '3', '4' ] + [ '5', '6' ] = '1,2,3,45,6'

Commented

x => y =>                   // given x and y
  eval(                     // evaluate as JS code:
    "for(;" +               //   loop:
      "(g = x =>" +         //     g = helper function taking x
        "r =" +             //       the result will be eventually saved in r
          "[...x + '']" +   //       coerce x to a string and split it
          ".sort() + ''" +  //       sort the digits and coerce them back to a string
      ")(y * x) +" +        //     compute g(y * x)
      "g(y / x) !=" +       //     concatenate it with g(y / x)
      "g(y) + r;" +         //     loop while it's not equal to g(y) concatenated with
    ")" +                   //     itself
    "++y"                   //   increment y after each iteration
  )                         // end of eval(); return y
\$\endgroup\$
  • \$\begingroup\$ 66: x=>F=y=>(g=x=>r=[...x+''].sort()+'')(y*x)!=g(y)|r!=g(y/x)?F(y+1):y May cause stack overflow if y is far from the solution tho. \$\endgroup\$ – Shieru Asakoto Sep 28 '18 at 2:21
  • \$\begingroup\$ or 75 using eval: x=>y=>eval("for(;(g=x=>r=[...x+''].sort()+'')(y*x)!=g(y)|r!=g(y/x);y++);y") \$\endgroup\$ – Shieru Asakoto Sep 28 '18 at 2:24
  • \$\begingroup\$ @ShieruAsakoto Thanks for the eval() idea. My first attempt was indeed recursive, but I gave up because of the high number of required iterations. \$\endgroup\$ – Arnauld Sep 28 '18 at 6:14
3
\$\begingroup\$

Haskell, 76 74 bytes

Two bytes shaved off thanks to Lynn's comment

import Data.List
s=sort.show
x#y=[n|n<-[y+1..],all(==s n)[s$n*x,s$n/x]]!!0
\$\endgroup\$
  • 1
    \$\begingroup\$ For the same byte count your f can be f x y=[n|n<-[y+1..],all(==s n)[s$n*x,s$n/x]]!!0 but then defining your answer as an operator saves two bytes: x!y=… and then your answer is (!) :) \$\endgroup\$ – Lynn Oct 7 '18 at 15:23
  • \$\begingroup\$ Didn't think of using list comprehensions! Thanks for the suggestion :D \$\endgroup\$ – umnikos Oct 7 '18 at 16:27
2
\$\begingroup\$

Japt, 24 bytes

Pretty naïve solution over a few beers; I'm sure there's a better way.

@[X*UX/U]®ì nÃeeXì n}a°V

Try it

\$\endgroup\$
  • \$\begingroup\$ Unfortunately this produces an incorrect result when x = 3 and y = 25000. \$\endgroup\$ – PerpetualJ Sep 27 '18 at 21:30
  • \$\begingroup\$ @PerpetualJ Assuming 315789473684210526 is the first solution for x=3, Javascript or Japt can't compute it correctly since it doesn't fit in double precision. \$\endgroup\$ – Bubbler Sep 28 '18 at 4:38
  • \$\begingroup\$ @PerpetualJ, fixed that earlier. That test case will never complete, though, for the reason Bubbler mentioned above. \$\endgroup\$ – Shaggy Sep 28 '18 at 10:13
  • \$\begingroup\$ @Shaggy This now produces a correct result and the solution that Bubbler pointed at is not the first correct result above 25000. See my test cases if you're curious on that. +1 \$\endgroup\$ – PerpetualJ Sep 28 '18 at 15:17
1
\$\begingroup\$

Python 2, 69 bytes

S=sorted
x,y=input()
while(S(`y`)==S(`y*x`)==S(`y/x`))<1:y+=1
print y

Try it online!

\$\endgroup\$
  • \$\begingroup\$ f=lambda x,y,S=sorted:y*(S(`y`)==S(`y*x`)==S(`y/x`))or f(x,y+1) should work, but it hits the recursion limit fairly quickly, and I don't know what PPCG rules have to say about that. \$\endgroup\$ – Lynn Oct 7 '18 at 13:48
1
\$\begingroup\$

Jelly,  14  13 bytes

-1 thanks to Erik the Outgolfer (`` uses make_digits, so D was not required)
+2 fixing a bug (thanks again to Erik the Outgolfer for pointing out the off-by one issue)

×;÷;⁸Ṣ€E
‘ç1#

A full program printing the result (as a dyadic link a list of length 1 is yielded).

Try it online!

How?

×;÷;⁸Ṣ€E - Link 1, checkValidity: n, x               e.g. n=285714,  x=2
×        -     multiply -> n×x                       571428
  ÷      -     divide -> n÷x                         142857
 ;       -     concatenate -> [n×x,n÷x]              [571428,142857]
    ⁸    -     chain's left argument = n             285714
   ;     -     concatenate -> [n×x,n÷x,n]            [571428,142857,285714]
     Ṣ€  -     sort €ach (implicitly make decimals)  [[1,2,4,5,7,8],[1,2,4,5,7,8],[1,2,4,5,7,8]]
        E    -     all equal?                        1

‘ç1# - Main link: y, x
‘    - increment -> y+1
   # - count up from n=y+1 finding the first...
  1  - ...1 match of:
 ç   -   the last link (1) as a dyad i.e. f(n, x)

Note that when the division is not exact the implicit decimal instruction (equivalent to a D) applied prior to the sort yields a fractional part
e.g.: 1800÷3D -> [6,0,0]
while 1801÷3D -> [6.0,0.0,0.33333333333337123]

\$\endgroup\$
  • \$\begingroup\$ I'm not really sure this answer is valid; the challenge requires the result to be "greater than y", which I interpret as "strictly greater than Y". Also, you don't need D. \$\endgroup\$ – Erik the Outgolfer Sep 28 '18 at 10:36
  • \$\begingroup\$ Ah good spot on >= I totally missed that! Had no idea had make_digits set on it - thanks. Will have to fix & update later though... \$\endgroup\$ – Jonathan Allan Sep 28 '18 at 12:29
1
\$\begingroup\$

Mathematica, 82 74 bytes

x=Sort@*IntegerDigits;Do[If[x[i#]==x@Floor[i/#]==x@i,Break@i],{i,#2,∞}]&

-8 bytes thanks to tsh

Function that takes arguments as [x,y]. Effectively a brute force search that checks if the sorted list of digits for y,y/x and xy are the same.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I'm not familiar with Mathematica. But it could be proved that the answer would still be right if you drop the fractional part of division: All ans, ans/x, ans*x should be divisible by 9. And this may make your solution shorter. \$\endgroup\$ – tsh Sep 28 '18 at 9:05
  • \$\begingroup\$ @tsh That works for x=3, but I'm not sure it's true for x=2. \$\endgroup\$ – Ørjan Johansen Sep 28 '18 at 9:32
  • \$\begingroup\$ @ØrjanJohansen Let v = a[1]*10^p[1] + a[2]*10^p[2] + ... + a[n]*10^p[n], u = a[1] * 10^q[1] + ... + a[n] * 10^q[n]. And u-v = a[1]*(10^p[1]-10^q[1]) + ... + a[n]*(10^p[n]-10^q[n]) Since 10^x-10^y=0 (mod 9) always holds. u-v=0 (mod 9) always holds. If there is an wrong answer w, since w*x-w=0 (mod 9), and, w-floor(w/x)=0 (mod 9): we have floor(w/x)=0 (mod 9). if floor(w/x)*x <> w, w-floor(w/x)*x>=9, but this conflict with the fact that w-floor(w/x)*x<x while x could be 2 or 3. \$\endgroup\$ – tsh Sep 28 '18 at 9:51
  • \$\begingroup\$ @tsh Thanks! For the benefit of others taking way too long to get this point, w=0 (mod 9) there follows from w*x-w=0 (mod 9) because x-1 is not divisible by 3. \$\endgroup\$ – Ørjan Johansen Sep 28 '18 at 10:17
  • \$\begingroup\$ If I exclude the IntegerQ test, it produces a couple of errors when it tries to do IntegerDigits on fractions, but Mathematica still goes past them and produces the correct answer. I'm not sure if errors being included during the calculation would be allowed, even if the final answer is correct. \$\endgroup\$ – numbermaniac Sep 28 '18 at 11:43
0
\$\begingroup\$

APL(NARS), 490 chars, 980 bytes

T←{v←⍴⍴⍵⋄v>2:7⋄v=2:6⋄(v=1)∧''≡0↑⍵:4⋄''≡0↑⍵:3⋄v=1:5⋄⍵≢+⍵:8⋄⍵=⌈⍵:2⋄1}
D←{x←{⍵≥1e40:,¯1⋄(40⍴10)⊤⍵}⍵⋄{r←(⍵≠0)⍳1⋄k←⍴⍵⋄r>k:,0⋄(r-1)↓⍵}x}
r←c f w;k;i;z;v;x;y;t;u;o ⍝   w  cxr
   r←¯1⋄→0×⍳(2≠T c)∨2≠T w⋄→0×⍳(c≤1)∨w<0⋄→0×⍳c>3
   r←⌊w÷c⋄→Q×⍳w≤c×r⋄r←r+c
Q: u←D r⋄x←1⊃u⋄y←c×x⋄t←c×y⋄o←↑⍴u⋄→0×⍳o>10⋄→A×⍳∼t>9
M:                     r←10*o⋄⍞←r⋄→Q
A: u←D r⋄→M×⍳x≠1⊃u⋄→B×⍳∼(t∊u)∧y∊u⋄z←r×c⋄v←D z⋄→C×⍳(⍳0)≡v∼⍦u
B: r←r+1⋄→A
C: k←z×c⋄⍞←'x'⋄→B×⍳(⍳0)≢v∼⍦D k
   ⎕←' '⋄r←z

test

  2 f¨250000 290000 3000000
xxxx 
1000000xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 
10000000xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 
285714 2589714 20978514 
 3 f¨ 31000000 290000000 
xxxxxxxxx 
100000000xxxxxxxxxxxxxxxxxxxxxxxxxx 
31046895 301046895 

I thought the problem as r a convenient number that can vary so one has the 3 numbers r, r*x, r*x*x in the way r begin to a value that r*x is near y (where x and y are inputs of the problem using same letters as main post). I used the observation that if the first digit of r is d than in r has to appear digits d*x and d*x*x too, for make r (or better r*x) one solution.

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 16 bytes

[>©Ð²÷s²*)€{Ë®s#

Try it online. (NOTE: Very inefficient solution, so use inputs close to the result. It works for larger inputs as well locally, but on TIO it'll time out after 60 sec.)

Explanation:

[                   # Start an infinite loop
 >                  #  Increase by 1 (in the first iteration the implicit input is used)
  ©                 #  Store it in the register (without popping)
   Ð                #  Triplicate it
    ²÷              #  Divide it by the second input
      s             #  Swap so the value is at the top of the stack again
       ²*           #  Multiply it by the second input
         )          #  Wrap all the entire stack (all three values) to a list
          €{        #  Sort the digits for each of those lists
             ®s     #  Push the value from the register onto the stack again
            Ë       #  If all three lists are equal:
               #    #   Stop the infinite loop
\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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