Thread: Intriguing numbers - again

  1. #1
    Registered User
    Join Date
    Oct 2005
    Posts
    3

    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. #2
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    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. #3
    Registered User
    Join Date
    Oct 2005
    Posts
    3
    Quote 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. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Comparing numbers to a list of numbers held in a text file
    By jmajeremy in forum C++ Programming
    Replies: 3
    Last Post: 11-06-2006, 07:56 AM
  2. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  3. Intriguing numbers
    By heartwork in forum C Programming
    Replies: 1
    Last Post: 10-06-2005, 08:20 AM
  4. the definition of a mathematical "average" or "mean"
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 12-03-2002, 11:15 AM
  5. A (complex) question on numbers
    By Unregistered in forum C++ Programming
    Replies: 8
    Last Post: 02-03-2002, 06:38 PM