Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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){}

}

}

share|improve this question
    
@Zev Chonoles Digits in the integer and fractional part. –  razpeitia Jun 15 '11 at 23:07
1  
@razpeitia: I think Zsigmondy's theorem is probably relevant. –  Zev Chonoles Jun 15 '11 at 23:14
1  
@raz: What $a$ is, is immaterial, if $t^b - 1 = 2^m 5^n$. For instance $t=9, b=2$. Pick any $a$ you like, the number will have finite representation. You are asking us to prove something that is wrong :-) –  Aryabhata Jun 15 '11 at 23:43
1  
Another thing that can happen is illustrated by $t=4,a=3,b=2$. Here $t^b-1=15\ne2^m5^n$, and $a\ne0\pmod b$, but $(t^a-1)/(t^b-1)=63/15=21/5=4.2$ is a terminating decimal. It might not be so easy to get a compact, useful description of the terminating cases. –  Gerry Myerson Jun 15 '11 at 23:56
1  
Note that your description of the problem is also incorrect: the site itself says, quote, 'establish whether $(t^a-1)/(t^b-1)$ is an integer with less than 100 digits'. If it's not an integer, it doesn't matter whether the fractional part is finite or not - they're looking for both 'integer' and 'less than 100 digits'. This is much easier to check, as the test to see if it's an integer is straightforward. –  Steven Stadnicki Jun 16 '11 at 1:55
show 11 more comments

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
Imagine that b is large $2^31 - 1$ and therefore $q = t^b-1$ is even more large. How can I find out (in a quick way) that $q$ has the form $2^m5^n$. –  razpeitia Jun 16 '11 at 0:09
    
@raz: $q = t^b -1$ need not be true, as Gerry's example shows (reduced form = after cancelling common factors). You might be able to do some factorization to try and figure out, but I guess that is the problem the contest is asking you to solve programmatically. –  Aryabhata Jun 16 '11 at 0:16
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). –  Gerry Myerson Jun 16 '11 at 0:58
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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