login
Positions of records in iterated MD5 applied to empty string.
4

%I #55 Sep 24 2023 08:48:27

%S 1,15,19,24,29,41,368,833,1582,12996,30527,105072,412282,571364,

%T 615279,641180,1213387,1635523,2603393,3505632,4289930,14230877,

%U 19306296,22032773,79279388,94146647,147017418,149333691,455566242,535859188,1429801665

%N Positions of records in iterated MD5 applied to empty string.

%C 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.

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

%C 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.

%C From _Ben Whitmore_, Apr 03 2018: (Start)

%C 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.

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

%C 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

%H Ben Whitmore, <a href="/A234849/b234849.txt">Table of n, a(n) for n = 1..38</a> (first 35 terms from Sean A. Irvine)

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/MD5">MD5</a>

%e a(2)=15 because MD5^{(15)}("")=d4f6f4e928303d5361d83531beb5260f is larger than MD^{(n)}("") for all n<15.

%e a(28)=149333691 because MD5^{(149333691)}("")=fffffff5fedfdd0975cc5bbd15245b22 is larger than all preceding values.

%t 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 *)

%o #!/bin/bash

%o function md5() {

%o echo -n "$1" | md5sum - | gawk '{print $1}'

%o }

%o it=0

%o while :; do

%o it=$[$it+1]

%o prev=$(md5 "$prev")

%o if [ "$prev" == "$best" ]; then

%o echo "Cycle detected"

%o exit

%o elif [ "$prev" \> "$best" ]; then

%o best=$prev

%o echo $it $prev

%o fi

%o done

%o (Python)

%o from hashlib import md5

%o def afind(limit):

%o record = hash = ""

%o for k in range(1, limit+1):

%o hash = md5(hash.encode('utf-8')).hexdigest()

%o if hash > record:

%o print(k, end=", ")

%o record = hash

%o afind(10**7) # _Michael S. Branicky_, Jul 02 2022

%o (C#)

%o public Enumerable<BigInteger> A234849()

%o {

%o yield return BigInteger.One;

%o var record = Convert.ToHexString(

%o MD5.HashData(Array.Empty<byte>())).ToLower();

%o var current = record;

%o for(var count = new BigInteger(2); ; count++)

%o {

%o current = Convert.ToHexString(

%o MD5.HashData(Encoding.UTF8.GetBytes(current))).ToLower();

%o var compareResult = string.Compare(current, record);

%o if (compareResult >= 0)

%o {

%o if(compareResult == 0)

%o {

%o yield break; // cycle detected

%o }

%o yield return count;

%o record = current;

%o }

%o }

%o } // _Delbert L. Johnson_, Mar 12 2023

%K nonn,fini,nice

%O 1,2

%A _Sean A. Irvine_, Dec 31 2013