2022 Developer Survey is open! Take survey.

# Tag Info

### How can I generate first n elements of the sequence 3^i * 5^j * 7^k?

Here I assume $0\in \mathbb N$. If you disagree start with $105$. Let $S$ be the sequence of numbers of the form $3^i5^j7^k$. Our task is to generate these numbers in order. Apart from $1$ each ...
Accepted

### What does the set {n | n is an integer and n = n + 1} represent?

But infinity isn't an integer. Since there is no integer $n$ such that $n=n+1$, you're right that the set is empty.
Accepted

### Why is the set of perfect squares in P?

A simple answer is "binary search". Keep track of a lower bound (starts out with 1) and an upper bound (starts out with $n$). In each iteration compute the midpoint $m$. In polytime check if $m∗m=n$. ...

### Goldbach Conjecture and Busy Beaver numbers?

The statement is about infinitely many numbers, but its demonstration (or refutation) would have to be a finite exercise. If possible. The surprise may come from the (false) assumption that finding ...

### Goldbach Conjecture and Busy Beaver numbers?

The idea from the author was that you can write a program in 100 lines (any fixed finite number here) which does the following: takes number x, tests conjecture. If not true then stop else continue on ...

### More details about the Baillie–PSW test

The advantage in using base 2 is that we know all of the psp's base 2 up to $2^{64}$. It has been verified that none of these psp(2)'s passes a Lucas test when the parameters $P, Q$ are chosen in ...

### Goldbach Conjecture and Busy Beaver numbers?

Aaronson has recently expanded in detail on this musing/ idea here working with Yedidia. they find an explicit 4888 state machine for the Goldbachs conjecture. you can read the paper to see how it ...
Accepted

### How to solve recurrences with transcendental terms?

The function $\log^\ast$ ("log-star", iterated logarithm), which shows up in complexity theory, is exactly the number of applications of $\log$ which reduce a number below some constant. (Confusingly,...
Accepted

### Determining if (infinite) binary language DFAs contain at least 1 prime?

It's a standard intro theory exercise that for any $d\ge 0$ there's a FA that accepts all and only those strings in $\{0, 1\}^*$ that are the binary representations of integer multiples of $d$. Thus, ...

### Least Common Non-Divisor

It is possible to improve on your second algorithm by using better algorithms for integer factorization. There are two algorithms for integer factorization that are relevant here: GNFS can factor an ...
Accepted

### Is the following intuition valid for understanding $k$-wise independent hash functions?

Your intuition is exactly right. Yes, that's equivalent to choosing a random polynomial over $\mathbb{F}_p$. The reason why it works is exactly the interpolation theorem for finite fields. $k$-wise ...
This isn't really computer science... You create a table d where you store the sum of the divisors of k, for k = 1 to M, where M = $5 · 10^6$. That's the part that is time critical. Then you create a ...