3
$\begingroup$

I'm a computer science student from Mexico and I have been training for the ICPC-ACM. So one of this problems called division sounds simple at first.

The problem is straight for you have and 3 integers $t$, $a$ and $b$, greater or equal than $0$ and less or equal than $2^{31} - 1$. Your job is simple, print the integer part of $\frac{t^a-1}{t^b-1}$ if the original number doesn't exceed 100 digits.

At first I think "It would be easy", I'll just check some tricky cases (like a = b or t = 0 or b=0 or a=0) and apply logarithms (to count the digits) if $(a-b)*\log(t) > 99$ then don't print else print the integer part.

But the problem (at least for me) here is know if $\frac{t^a-1}{t^b-1}$ doesn't exceed 100 digits including the fractional part.

Test case: $t = 2; a = 3; b = 2;$ then $\frac{t^a-1}{t^b-1}=\frac{2^3-1}{2^2-1}=\frac{7}{3}=2.333333...$ witch obviously have more than 100 digits.

After searching a little bit I found this page and if you take a look it's just matter of check some cases, that I have already checked except for this one if a % b != 0 then not a integer with less than 100 digits.

I put that condition in my code and It worked! But I'm a want a simple (if possible) explanation of why $\frac{t^a-1}{t^b-1}$ has more than 100 digits if $a \mod b \neq 0$.

Update: Full and accepted code here:

import java.io.*; import java.math.BigInteger;  public class Main {  private static BigInteger f(BigInteger x, BigInteger k){     if(k.equals(BigInteger.ONE))         return BigInteger.ONE;     if(k.testBit(0)){         return (x.add(BigInteger.ONE).multiply(f(x.pow(2), k.divide(new BigInteger("2"))))).multiply(x).add(BigInteger.ONE);     }     else{         return x.add(BigInteger.ONE).multiply(f(x.pow(2), k.divide(new BigInteger("2"))));      } }  private static String D(long t, long a, long b){     BigInteger T = new BigInteger(t+"");     BigInteger A = new BigInteger(a+"");      BigInteger B = new BigInteger(b+"");     return f(T.pow((int)b), A.divide(B)).toString(); }  public static void main(String[] args) {     BufferedReader input = new BufferedReader(new InputStreamReader(System.in));     String line;     String lines[];     long a, b, t;     try{         while(true){             line = input.readLine();             if(line == null)                 break;             lines = line.split("[ ]+");              t = Long.parseLong(lines[0]);             a = Long.parseLong(lines[1]);             b = Long.parseLong(lines[2]);             System.out.print("("+t+"^"+a+"-1)/("+t+"^"+b+"-1) ");             if(t == 1)                 System.out.print("is not an integer with less than 100 digits.\n");             else if(a == b)                 System.out.print("1\n");             else if(b == 0)                 System.out.print("is not an integer with less than 100 digits.\n");             else if(a == 0)                 System.out.print("0\n");             else if(a % b != 0)                 System.out.print("is not an integer with less than 100 digits.\n");             else if((a - b)*Math.log10((double)t) > 99f)                 System.out.print("is not an integer with less than 100 digits.\n");             else                 System.out.print(D(t, a, b)+"\n");          }     }     catch(IOException e){}  } 

}

  • 0
    @razpeitia Oh, I understand that your hypothesis is wrong - what I'm noting is that your characterization of the problem being asked itself is misguided; you're essentially asking the wrong question. If you want to ask 'how can I know when $(t^a-1)/(t^b-1)$ is an integer, and how can I find out how many digits it has?', that's another question, and as it turns out an interesting one in its own right - but that's closer to the question you should be asking than the one you did is.2011-06-16

2 Answers 2

2

Just for closure, what you are asking us to prove is wrong.

A couple of counterexamples:

$\dfrac{3^3 - 1}{3^2 - 1}$

$\dfrac{4^3 - 1}{4^2 - 1}$ (see Gerry's comment)

In general if $\dfrac{t^a - 1}{t^b - 1} = \dfrac{p}{q}$ in reduced form, and $q = 2^n 5^m$ then the number has a finite representation (in base 10). See this: http://en.wikipedia.org/wiki/Decimal_representation#Finite_decimal_representations

  • 1
    @razpeitia, if $b$ is that large, you may be able to prove that the quotient has more than 100 digits no matter what $t$ and $a$ are (trivial examples aside).2011-06-16
4

Aryabhata's counterexamples are based on finding integers $a, n \ge 2$ such that $a^n-1$ is of the shape $2^s5^t$. We show that there are not many such counterexamples. (there is nothing here about counterexamples of Myerson's type.) In order to save some words, call the numbers of shape $2^s5^t$ bad.

The case $n$ even: Imagine first that $n$ is even, say $n=2m$. We want $a^{2m}-1$ to be bad.

Suppose first that $a$ is even. Then $a^{2m}-1$ is odd. If it is bad it must have shape $5^t$. It is clear that $t \ne 1$. So if $a^{2m}-1$ is bad, there is a solution of the exponential diophantine equation $2^n-5^t=1$ with $n, t >1$. This contradicts Mihailescu's Theorem, aka the Catalan Conjecture. We could give elementary proofs of the Catalan Conjecture for the small number of cases we quote it, but this solution is already much too long.

Suppose next that $a$ is odd. Note that $a^{2m}-1=(a^m-1)(a^m+1)$, and these two numbers have greatest common divisor $2$. Let $c=a^m$. So $(c-1)(c+1)$ is bad. There are two possibilities. Either $c-1$ is a power of $2$ and $c+1$ is twice a power of $5$ (which could be $5^0$) or the other way around.

In the first case, $c-1=2^k$, $c+1=(2)5^t$, which gives $2^{k-1}+1=5^t$. This has solution $k=3$, $t=1$, and, by Mihailescu's Theorem, no other solutions. In the second case, we get $5^t+1=2^{k-1}$, which has solution $t=0$, $k=1$, and no other solutions.

The case $n$ odd: We next look for solutions with $n>2$ and odd. We want $a^n-1$ to be bad. If $a$ is even, then $a^n-1$ is odd, so if it is bad it is of shape $5^k$. This contradicts Mihailescu's Theorem.

So look for solutions with $a$ odd. Since $a-1$ divides $a^n-1$, $a-1$ must be bad. There are two cases to consider: (i) $a-1$ is divisible by $5$ and (ii) $a-1$ is not divisible by $5$, and hence is a power of $2$.

Case (i): Note that since $n$ is odd, $a^{n-1}+a^{n-2}+ \cdots +1$ is odd. If $a^n-1$ is to be bad, the preceding sum must be a power of $5$. Since $a \equiv 1 \pmod{5}$, it follows that $n \equiv 0 \pmod{5}$. Since $n$ is a multiple of $5$, it follows that $a^5-1$ divides $a^n-1$. And since $a^n-1$ is bad, so is $a^5-1$. We show this is impossible.

Since $a\equiv 1 \pmod{5}$, $a$ is congruent to one of $1$, $6$, $11$, $16$, or $21$ modulo $25$. For each of these possibilities, compute $1+a+a^2+a^3+a^4$ modulo $25$. In none of the cases do we get $0$. Since it is clear that $1+a+a^2+a^3+a^4>5$, this contradicts the fact that this sum is a power of $5$.

Case (ii): Suppose that $a-1$ is a power of $2$. Then $a$ is congruent to one of $0$, $2$, $3$, or $4$ modulo $5$.
If $a$ is a multiple of $5$, then $5$ cannot divide $a^n-1$, so $a^n-1$ is a power of $2$, which is impossible. This is also the case if $n$ is congruent to $2$, $3$, or $4$ modulo $5$, since no odd power of any of these can be congruent to $1$ modulo $5$.