1
$\begingroup$

I had a difficult assignment in my Data Structures and Algorithms class.

We need to implement a program that computes a function f(n) based on the following known values of n and f(n):

n : 9689 9941 11213 19937 21701 23209 44497 86243 110503 132049

f(n) : 3 5 7 13 17 19 23 37 47 59

n : 216091 756839 859433 1257787 1398269 2976221 3021377

f(n) : 61 67 71 79 89 101 103

The requirements of the assignment are as follows:

  1. We are allowed to use a pre-initialized array with 17 numbers.
  2. We can use one XOR operation and one MOD operation.
  3. We can access the array in a read-only manner.
  4. The program should not crash if an input n is not listed. The output can be arbitrary in such cases.

Another requirement may be to minimize operations and memory usage.

The first thing I want to know is what knowledge I should apply to this problem. I have currently written a program that stores f(n) in an array and when we enter n, takes the remainder of each input n and each number in the array. I printed out the results to try to be able to get some insight. But I wasn't. My other thought is that maybe this question has something to do with hashing, but I don't have a clue. My biggest doubt is how should we use XOR in the question.

I am open to suggestions and alternative approaches. Thank you in advance!

$\endgroup$
3
  • 1
    $\begingroup$ Does or doesn't a pre-initialized array with 17 numbers mean an array of size 17? The task may be simpler with a 23-element array, trivial with a 3020100 element one. $\endgroup$
    – greybeard
    Commented May 20 at 17:38
  • $\begingroup$ In the task is what I wrote above. My understanding is that it can be thought of as an Array of size 17 $\endgroup$
    – Shiyao Ju
    Commented May 20 at 19:52
  • $\begingroup$ If you look at the seventeen function values provided, they all share a particular mathematical property. Coincidence? I think not. $\endgroup$
    – njuffa
    Commented May 21 at 11:42

1 Answer 1

1
$\begingroup$

As we want to use both operations, we only have two possible combinations: $$\left(n \oplus x\right) \mod s\tag{1}\label{1}$$ $$\left(n \mod x\right) \oplus s\tag{2}$$

If we store $f\left(n\right)$ in an array $a$ of length $17$, we want our index $i$ to lie within the interval $\left[0,16\right]$. We can achieve this by choosing $\eqref{1}$ with $s = 17$.

Now we need to find $x \;\forall\; n : a\left[\left(n\oplus x\right) \mod 17\right]=f\left(n\right)$

Considering that we can store our elements $f\left(n\right)$ in $a$ in any order, this problem can be brute forced quite easily.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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