4
$\begingroup$

For a given number $n$ I want to find the lowest integer multiple of $n$ that is represented in decimal as the following regular expression: $[4]^+[0]^*$

Examples of numbers that are generated by that regex are: 4, 40, 44, 400, 440, 444

Notice that 404 is not a member.

So far what I figured out experimentally is that for a given number $n$ composed of two prime factors $p_1$ and $p_2$ the number of $4$s is $(p_1-1)(p_2-1)/2$.

Does anyone know an exact formula for figuring out the number of $4$s and $0$s in the minimum multiple described above?

$\endgroup$
7
  • $\begingroup$ what does [4]*[0] mean $\endgroup$ Jun 12, 2017 at 20:11
  • $\begingroup$ it's a regex to describe the number in decimal format $\endgroup$
    – ppaulojr
    Jun 12, 2017 at 20:12
  • $\begingroup$ @SakethMalyala it means zero or more 4 followed by one or more 0 $\endgroup$
    – miracle173
    Jun 12, 2017 at 20:36
  • $\begingroup$ @ppaulojr 4, 44, 444 do not satisfy this regualr expression. Ther must be at least one trailing 0. but, 0, 00, 000 satisfy the expression. $\endgroup$
    – miracle173
    Jun 12, 2017 at 20:38
  • $\begingroup$ @ppaulojr a simpler notation is 4*0+ there are no brackets needed. $\endgroup$
    – miracle173
    Jun 12, 2017 at 20:40

1 Answer 1

2
$\begingroup$

First, factor $n$ into $2^a5^bc$ The number of zeros will be $\max(a-2,b)$ where the $-2$ comes from the $4$s in your number. The number of $4$s will be the length of the repeat in the decimal of $\frac 1c$, which is the minimum $k$ such that $10^k \equiv 1 \pmod c$ except that if you have a factor of $3$ you multiply by $3$ and if you have a factor $9$ you multiply by $9$.

$\endgroup$
6
  • $\begingroup$ It seems correct, but how did you figure this out? $\endgroup$
    – ppaulojr
    Jun 12, 2017 at 20:12
  • $\begingroup$ Basically you need $c$ to divide into a repunit, a number of the form $1111$, so you can multiply it by $4$ to get the number you are looking for. The special rules for $3$ and $9$ come about because $3$ divides $10-1=9$, but you need to be thinking of $3$ dividing $111$ which you can multiply up to $444$. $\endgroup$ Jun 12, 2017 at 20:26
  • $\begingroup$ But how did you figure this out so quickly? What previous knowledge did you use here @RossMillikan $\endgroup$
    – JBernardo
    Jun 12, 2017 at 20:35
  • $\begingroup$ I wonder that too. Which theorems did you use to reach this formula. The repunit part is puzzling me. #kudos for the answer $\endgroup$
    – ppaulojr
    Jun 12, 2017 at 20:46
  • 1
    $\begingroup$ Consider for example $1/41 = 0.0243902439...$ This number is also equal to $\frac{2439}{99999}$, which means that $99999 = 9\cdot11111$ is a multiple of 41 (and since 41 is not a multiple of 3, 11111 is a multiple of 41). Indeed, 11111 is the smallest such "repunit" that is a multiple of 41, or else 1/41 would repeat with a smaller period. (e.g. 1/41 is also equal to $\frac{243902439}{9999999999}$... but 10 isn't the smallest repeating chunk.) So @RossMillikan counting the length of the repeating unit of $1/c$ gives you the smallest number of the form $111...11$ that is a multiple of $c$. $\endgroup$ Jun 12, 2017 at 21:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .