All Questions
17
questions
8
votes
0
answers
314
views
Harmonic Numbers' Numerators Divisible by a Prime $p$
For a prime $p$, I am trying to determine the set of all $n$ for which the numerator of $H_n$ is divisible by $p$, with $H_n$ being the $n$'th harmonic number.
After going through a lot of literature, ...
- 1,022
2
votes
1
answer
90
views
How to encode a set of whole numbers $\{a_1,a_2,...,a_n\}$ such that given a number $x$ we can test if $x \in \{a_1,a_2,...,a_n\}$
Suppose we have a set of whole numbers $\{a_1,a_2,...,a_n\}$. Is there a way to encode them into a new number $e$ such that we can use $e$ to test if a given number $x \in \{a_1,a_2,...,a_n\}$? So ...
- 163
1
vote
1
answer
73
views
Pairing $2n$ real numbers
Let $\{l_1,l_2,\dots,l_{2n}\}$ be a set of real numbers.
I need to divide those numbers into -$n$- pairs such that the sum of their multiplications (of each pair) will be as maximum as possible.
I ...
- 63
0
votes
0
answers
1k
views
Is a one to one function also a total function
One of the lines in my lecture slides for theory of Computation states that
A is equipotent to B (|A|=|B|) if there is bijection f: A->B
Which means that f is both one to one and onto. Since f is ...
- 101
0
votes
0
answers
20
views
generating families of "non dense" integers
I was considering finite lists of integers, and I defined a notion of "density". That is a list of integers $X$ has density $p$ if $G$ is the size of all unique sums of subsets of $X$ and $p = |G|/|X|$...
- 17.5k
3
votes
1
answer
86
views
Difference sets without squares of Integers
I am trying to print numbers occuring in A030193
i.e Let S = set of square numbers; a(0)=0; a(n) = smallest m such that m - a(i) is not in S for all i < n.
but I am unable to do it in better ...
1
vote
2
answers
95
views
Why do combinations have each element appear an equal number of times?
Say you have a set s = {1, 2, 3}. All of the possible combinations of that set would be 12, 13, 23. Note that there are 2 1s, 2 2s, and 2 3s. Is there any way to prove that this is true for any set ...
- 55
1
vote
1
answer
196
views
How many non decreasing sequence of length k is possible?
If we have a set like this { 1A ,2A ,2B, 3A, 3B, 3C}, how many non decreasing sequence is possible, such that number in left is less than number in right of length k?
i.e,
Length = 2 then the ...
6
votes
1
answer
4k
views
Why in RSA, the public exponent $e$ must be coprime with $\phi (n)$
I'm trying to understand the RSA cryptosystem, and that's what I know so far:
If we think about some number $m$ as the message, then we are searching a $e$ and $d$ such that
$$m^{ed} \equiv m \ \ (\...
- 6,756
3
votes
2
answers
925
views
Hash with Chaining Problems
I ran into an example in Computer Science Course.
suppose we use Hashing with chanining and use table of size m. the hash function map record with key ...
- 203
1
vote
1
answer
114
views
How many integers could be in such a way that any digits is not bigger than the left digits?
How many 4-digits integers could be in such a way that any digits is not bigger than it's left digits?
I Try it with simulation, i get 714. anyone could describe a formula for me?
My try:
- 217
2
votes
2
answers
125
views
Nice Question in Mathmatics about Times
I ran into a nice question from one book in Discrete Mathematics. I want to someone lean me how solve such a problem, because I prepare for entrance exam.
if the time is "Wednesday 4 ...
- 432
1
vote
1
answer
264
views
Proof that such a Turing machine cannot be constructed...
Prove there can be no Turing machine $M^*$ that takes input $n$ and:
i. halts printing 1 if $M_n$ halts on input 1
ii. halts printing 0 if $M_n$ doesn't halt on input 1
Intuitively I can see why ...
- 1,705
0
votes
2
answers
2k
views
Tough Turing machine multiple choice questions
I'm having a tough time deciding whether my answers for these questions are correct. Can anyone help me agree on something? They seem pretty easy, but I've found that they're actually difficult.
(...
- 1,705
1
vote
1
answer
325
views
Communication complexity example problem
Let $G = (V,E)$ and $H = (W,F)$ be two undirected graphs with $|V| = |W| = n$.
G and H are isomorphic if there is a bijection f : V -> W such that:
$\{u,v\} \in E$ <=> $\{f(u),f(v)\} \in F$
...
