Radcliffe’s gists

Radcliffe / powermod.erl

Created August 23, 2018 01:56

Fast modular exponentiation in Erlang

	-module(powermod).
	-export([powmod/2]).

	powmod(A, B, M) -> powmod(A, B, M, 1).
	powmod(_, 0, _, R) -> R;
	powmod(A, B, M, R) when B rem 2 == 1 -> powmod(A, B-1, M, A*R rem M);
	powmod(A, B, M, R) -> powmod(A*A rem M, B div 2, M, R).

Radcliffe / pwned.py

Created January 21, 2019 02:16

Python 3 script to search for exposed passwords

	#!/usr/bin/env python3
	#
	# This Python script searches a database of over 500 million passwords
	# to determine whether a given password has been exposed in a data breach.
	#
	# Thanks to Troy Hunt for creating the API that is used by this script.
	# See https://haveibeenpwned.com/API/v2#PwnedPasswords for more information.
	#
	# Author: David Radcliffe ([email protected])
	# Date: 20 January 2019

Radcliffe / 314prime.txt

Created March 3, 2019 18:15

A 314 prime for Pi Day: A 3141 digit probable prime, with random digits chosen from 3, 1, and 4, starting with 314.

Radcliffe / tower_mod.py

Created March 26, 2019 01:53

Calculating the last 100 digits of 9^9^9^9 with Python

	def phi_2_5(m):
	"""Computes the totient of a number m whose only prime factors are 2 or 5."""
	if m % 2 == 0:
	m //= 2
	if m % 5 == 0:
	m = (m * 4) // 5
	return m

	def tower_mod(a, n, m):
	"""Evaluates the power tower a^a^a^..^a, with height n, modulo m.

Radcliffe / binom.py

Created June 1, 2019 21:16

Binomial coefficient in Python

	# Python script to calculate the binomial coefficient C(n, k)
	# where n is an integer or floating point number and k is an integer.
	#
	# We use the following general definition:
	# C(n, k) = n(n-1)(n-2)...(n-k+1) / k! if k >= 0,
	# 0 if k < 0.
	#
	# For n < 0, we use the negative binomial identity
	# C(n, k) = (-1)^k * C(k - n - 1, k)
	#

Radcliffe / a308479.py

Last active June 10, 2019 01:40

Least k such that k*n and (k+1)*n fail to have a common nonzero digit

	# This script calculates Sequence A0308479, the least k such that kn and (k+1)n
	# fail to have a common nonzero digit, or 0 if this property never occurs.
	#
	# See: https://oeis.org/A308479
	#
	# Author: David Radcliffe
	# 9 June 2019

	def share_digit(m, n):
	return set(str(m)) & set(str(n)) - set('0')

Radcliffe / generalized-coupon.py

Created October 25, 2019 21:06

Coupon Collector problem with unequal probabilities

	"""
	A generalized coupon collector problem.

	An experiment with n possible outcomes is repeated until each of the possible
	outcomes is observed at least once. Each outcome i has a fixed non-zero
	probability p[i], and each trial is independent of the previous trials.
	What is the expected number of trials?

	For example, what is the expected number of times that two dice must be rolled
	until all of the possible totals (from 2 to 12) have appeared at least once?

Radcliffe / circular_sudoku_graph.py

Created December 26, 2019 05:32

Draw the Sudoku graph with a circular layout

	"""
	This script draws a Sudoku graph with the vertices arranged in a circle.

	David Radcliffe
	[email protected]
	25 December 2019

	The sudoku_graph() function below is being considered for a future version of NetworkX.
	"""

Radcliffe / sperner2020.txt

Created December 28, 2019 03:08

Happy 2020, Emanuel Sperner!

	There are 2020 ways to choose 4 nonempty subsets of {1,2,3,4,5} so that no set contains another.
	(Sperner systems with 4 blocks)


	{{1}, {2}, {3}, {4}}
	{{1}, {2}, {3}, {5}}
	{{1}, {2}, {3}, {4, 5}}
	{{1}, {2}, {4}, {5}}
	{{1}, {2}, {4}, {3, 5}}
	{{1}, {2}, {3, 4}, {5}}

Radcliffe / circle_plot.py

Last active January 27, 2020 16:22

Circle plot for the state vector of a quantum register

	# File: plot_circles.py
	#
	# This code is used with Qiskit to display the circle plot representation of the state vector
	# of a quantum register. The state vector for an N-qubit quantum register has 2^N components,
	# which are called amplitudes. Each amplitude is a complex number, and the squared magnitudes
	# add up to 1.
	#
	# The circle plot has a circle of radius 1 for each amplitude, with a filled-in circle inside it.
	# The radius of the filled-in circle is equal to the magnitude. The circle also contains a line
	# segment from the center of the circle to the circumference. The line segment is rotated to show

David Radcliffe Radcliffe