   number theory
  given three numbers D,N and T i want to chekc if the following is true or false:any number in D-system with N digits(which are consecutive- but i do not care about the row) will be divided by T..example if D=10, N=3 , T=3the sentence is true because every number with 3 consecutive digits will be divide by T=3 (for example consider 123, 231, 456, 546...)2<=D<=10241<=N<=10241<=T<=1024any ideas for a general algorithm??   
  One idea is that, in your example, what you are saying is true because both 123 and 111 are multiples of 3. In general, you can write "111...1" (N ones) in base D as (D^N-1)/(D-1). "123...N" is a bit trickier, but I think it ends up being ((D^N-1)*D/(D-1)-N)/(D-1).So the general algorithm would go something like this:* For each value of N an D (2^20 iterations):  * Compute the G = gcd((D^N-1)/(D-1),((D^N-1)*D/(D-1)-N)/(D-1))  * Compute all the divisors of G, and print them out as possible values for T.;  Well as far as I get it,it should be enough to solve the problem for a system of your choosing (for example D = 10).If a is divided by b in decimal,then a will be divided by b in an arbitrary system.So there are three steps to do what you want :1) You need a function to convert a number from any system to decimal.2) You need to generate all the permutations that are required by your task.3) For each number in the list,convert it to decimal and check if it is divided by T. If any number fails the division,return false.Otherwise return true.   ;  A number in base D, can be written as ∑ ci DiUsing the two equivalencesab mod T = (a mod T)(b mod T) mod Tand(a + b) mod T = (a mod T) + (b mod T) mod T,you can write that number only using numbers in the equivalence classes mod T. In your example10i mod 3 = 1so the sum become(c0 + c1 + c2) mod 3and using the fact they are consecutive all the sums become equal to(0 + 1 + 2) mod 3 = 0 mod 3The general case is a lot more difficult but, using modules you can greatly reduce the number of cases you have to test.;  Disclaimer: I don't write proofs often, so it's likely I made a mistake somewhere, but I think the following might be correct:a = digits of your number A, of length Nthe the number itself issum(a * D^i), with i <- [0..N - 1]if T divides this number, thensum(a * D^i) = 0 mod Tand alsosum(a * D^i) = 0 mod p^efor any prime exponent that divides TNow we have 2 cases:D = 1 mod p^eD != 1 mod p^eD != 1 mod p^e:In this case, D^0 = 1 mod p^e, and D^1 will be something else, so a solution will be of the form:(there must always be an a[0] and a[1] who's difference won't be 0 mod p)a[0] + a[1] * D + ... = 0 mod p^eNow lets take the permutation with a[0] and a[1] swapped:a[1] + a[0] * D + ... = 0 mod p^eThe difference between those two sums should of course also be 0, so(a[0] - a[1]) + (a[1] - a[0]) * D == 0 mod p^e(a[0] - a[1]) - (a[0] - a[1]) * D == 0 mod p^e(a[0] - a[1]) == (a[0] - a[1]) * D mod p^ebut this can only be true if D = 1 mod p^e, so we have a contradiction.case D = 1 mod p^e:D^i is always 1 mod p^e, so sum(a * D^i) equals sum(a)If p^e divides N, then for every a, we can find an a[j] = -a mod p, so they sum to zero.If p^e does not divide N, then for any sequence that does sum to 0 mod p, increasing all of a by one will sum to N mod p, so then not all A of length N are divisible by p^eConclusion:So your condition holds whenD = 1 mod p^efor every p^ewhich means D = 1 mod Tand T must divide N:N = 0 mod T[Edited by - quasar3d on June 6, 2010 1:15:02 PM];  thanks all for yor help.. i have found the answer.. its very similar to the last post but a little bit different.. thanks for your time..   ;Quote:If p^e divides N, then for every a, we can find an a[j] = -a mod p, so they sum to zero.Here I made a mistake. This only holds for odd primes. For powers of 2, 2 * p^e should divide N.So is the answer you foundD = 1 mod TT even:N = 0 mod 2*TT odd:N = 0 mod T   