Intriguing numbers - again
I wrote yesterday:
"Consider in some base B numbers of N1 x N2 digits, N1 "groups" each made by N2 digits.
(for ex. N2=8 & B=2 we have N1 "octets")
For all pairs of 2 digits in any 2 positions let say i,j as b_i,b_j in the same group one may define the difference:
d(i,j) = b_j - b_i
If we take in any other group a pair in the same positions i,j the difference must not be equal with -d(i,j)
Can someone write a C code such that:
- at input reads 2 positive integers N1 & N2 at most 20;
- outputs the smallest base B for which such number exists & one of these intriguing numbers!"
The post was locked - maybe I did not try to solve it. Sorry!
This is not a homework... I have tried to develop a formula for B as function of the number of digits N=N1 x N2 or at least delivering some reasonable bounds...
I'm not using C programming too often and I'm not quite familiar...Basically I know how this can be solved.
Clearly B is (brute) upper bounded by N and there is a B(N) s.th. for all B < B(N) there are no "intriguing numbers"...
For such B's is the same if we use brute search or backtracking to prove there is no solution! Then increment B until we will find a solution.
Brute force: write all B^N numbers and use a function which check if the number is intriguing or not: check for each digit from the most significant in the case if it is not the 1st in group, if the differences regarding the previous digits in group are unequal with the differences in the switched similar positions in all the previous groups.
Backtracking: develop a number digit by digit from the most significant - when you add a new digit check the difference conditions. If it is not possible try the next digit in base. If at some digit we have no more digits available in base B perform the backtracking step.
Thanks for ur time,
