Skip to main content
2 of 2
added 49 characters in body; edited title
Turbo
  • 13.9k
  • 1
  • 27
  • 76

On a definition of sensitivity of primes in base-$2$

Given an odd integer in $\mathbb Z_{\geq0}$ of $n$ bits let $a_{n-1}a_{n-2}\dots a_1a_0$ be its binary expansion where $a_{n-1}=a_0=1$.

Call an $n$ bit prime $f(n)$-sensitive (similar to sensitivity of Boolean functions) if we flip any $f(n)$ of its $n-2$ bits $a_{n-2}\dots a_1$ the resulting $n$ bit odd number is not prime.

  1. Do we know how large $f(n)$ can be at least under any reasonable conjectures?

I think $f(n)=\Omega(\log n)$ might be known but $f(n)=\omega(\log n)$ might be possible.

  1. Do we know at least average case behavior of $f(n)$?
Turbo
  • 13.9k
  • 1
  • 27
  • 76