A234849 Positions of records in iterated MD5 applied to empty string.

1, 15, 19, 24, 29, 41, 368, 833, 1582, 12996, 30527, 105072, 412282, 571364, 615279, 641180, 1213387, 1635523, 2603393, 3505632, 4289930, 14230877, 19306296, 22032773, 79279388, 94146647, 147017418, 149333691, 455566242, 535859188, 1429801665

Offset

1,2

Comments

The MD5 message digest algorithm converts a string into a 128-bit number represented as a 32-digit lowercase hexadecimal string. Consider iterating this function starting with the empty string, MD5("") = d41d8cd98f00b204e9800998ecf8427e, MD5^{(2)}("") = MD5("d41d8cd98f00b204e9800998ecf8427e") = 74be16979710d4c4e7c6647856088456.

The sequence gives the iteration numbers where a record value is achieved.

Because each iteration produces a 128-bit number, the sequence must be finite, although it is unknown what the maximum value attained by the above iteration is.

From Ben Whitmore, Apr 03 2018: (Start)

It appears likely that a(39) will be much larger than a(38). This is because the first 46 bits of MD5^{a(38)}("")=fffffffffffcfade870a33bf9bba701c are all 1's, while a(38) < 2^40 << 2^46.

a(39) > 2^40. (End)

Each iteration consists of converting the previous 16-byte MD5 hash result into a 32 byte lowercase hexadecimal string, and then taking the MD5 hash of that. This sequence only includes values that reach a new maximum. - Delbert L. Johnson, Mar 12 2023

Links

Ben Whitmore, Table of n, a(n) for n = 1..38 (first 35 terms from Sean A. Irvine)

Wikipedia, MD5

Example

a(2)=15 because MD5^{(15)}("")=d4f6f4e928303d5361d83531beb5260f is larger than MD^{(n)}("") for all n<15.
a(28)=149333691 because MD5^{(149333691)}("")=fffffff5fedfdd0975cc5bbd15245b22 is larger than all preceding values.

Mathematica

f[w_] := FromDigits[If[# < 57, # - 48, # - 87] & /@ Flatten[ToCharacterCode /@ Characters@ w], 16]; With[{s = f /@ Rest@ NestList[Hash[#, "MD5", "HexString"] &, "", 2^16]}, Map[FirstPosition[s, #][[1]] &, Union@FoldList[Max, s]]] (* Michael De Vlieger, Apr 07 2018, Version 11.3 *)

Prog

#!/bin/bash
function md5() {
    echo -n "$1" | md5sum - | gawk '{print $1}'
}
it=0
while :; do
    it=$[$it+1]
    prev=$(md5 "$prev")
    if [ "$prev" == "$best" ]; then
        echo "Cycle detected"
        exit
    elif [ "$prev" \> "$best" ]; then
        best=$prev
        echo $it $prev
    fi
done
(Python)
from hashlib import md5
def afind(limit):
    record = hash = ""
    for k in range(1, limit+1):
        hash = md5(hash.encode('utf-8')).hexdigest()
        if hash > record:
            print(k, end=", ")
            record = hash
afind(10**7) # Michael S. Branicky, Jul 02 2022
(C#)
public Enumerable<BigInteger> A234849()
{
    yield return BigInteger.One;
    var record = Convert.ToHexString(
          MD5.HashData(Array.Empty<byte>())).ToLower();
    var current = record;
    for(var count = new BigInteger(2); ; count++)
    {
        current = Convert.ToHexString(
           MD5.HashData(Encoding.UTF8.GetBytes(current))).ToLower();
        var compareResult = string.Compare(current, record);
        if (compareResult >= 0)
        {
            if(compareResult == 0)
            {
                yield break; // cycle detected
            }
            yield return count;
            record = current;
        }
    }
} // Delbert L. Johnson, Mar 12 2023

Crossrefs

Sequence in context: A077349 A368827 A257020 * A164564 A211329 A104298

Adjacent sequences: A234846 A234847 A234848 * A234850 A234851 A234852

Keyword

nonn,fini,nice

Author

Sean A. Irvine, Dec 31 2013

Status

approved