# Thread: Intriguing numbers - again

1. ## 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,

2. I don't know the math of that problem either -- but work out the math with pencil & paper first. If you can't do that then you won't be able to do it with a computer either.

3. Originally Posted by Ancient Dragon
I don't know the math of that problem either -- but work out the math with pencil & paper first. If you can't do that then you won't be able to do it with a computer either.
I think it can be done with brute force / backtracking - I wonder if there is some other nicer / optimized solution...
The problem is when N1, N2 are larger than 10 and we achieve for check the base B=10, then there are more than 10^100 numbers to be checked, which seems to take hours / days of CPU time... That's why you said "you won't be able to do it with a computer either"!

4. > That's why you said "you won't be able to do it with a computer either"
Actually, it's more fundamental than that - if you can't do the math (abeit slowly) on paper, then no amount of machine time will help if you can't express your algorithm (as written on paper) in code.

> The post was locked - maybe I did not try to solve it. Sorry!
Well dumping what looks like homework (whether you say it is or isn't doesn't matter) without effort will get it locked.

> I think it can be done with brute force / backtracking - I wonder if there is some other nicer / optimized solution...
Try a board which specialises in esoteric maths then.