9
\$\begingroup\$

It can be proven that there's exactly one string of infinite length that remain same after base64 encoding Vm0wd2QyUXlVWGxWV0d4V1YwZ...

Given a position, output the character on that position.

Your program would be run on AMD Ryzen 5 5500U@4GHz given 4GB memory and 1 minute (may decrease if RAM turns out to be hard limit). You can take input in any base, but not one number in two different bases. No multithread allowed. Largest handled range wins.

Test cases: (Position \$3^k+b\$, 0-base. Notice that \$3^0=1\$ so \$b\$ starts at -1)

  \b -          111111111122222222223333333333444444444455555555556666666666777777777788888888889999999999
  k\ 10123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789
   0 Vm0wd2QyUXlVWGxWV0d4V1YwZDRWMVl3WkRSV01WbDNXa1JTVjAxV2JETlhhMUpUVmpBeFYySkVUbGhoTVVwVVZtcEJlRll5U2tWV
   1 0wd2QyUXlVWGxWV0d4V1YwZDRWMVl3WkRSV01WbDNXa1JTVjAxV2JETlhhMUpUVmpBeFYySkVUbGhoTVVwVVZtcEJlRll5U2tWVWJ
   2 UXlVWGxWV0d4V1YwZDRWMVl3WkRSV01WbDNXa1JTVjAxV2JETlhhMUpUVmpBeFYySkVUbGhoTVVwVVZtcEJlRll5U2tWVWJHaG9UV
   3 RWMVl3WkRSV01WbDNXa1JTVjAxV2JETlhhMUpUVmpBeFYySkVUbGhoTVVwVVZtcEJlRll5U2tWVWJHaG9UVlZ3VlZadGNFSmxSbGw
   4 TVVwVVZtcEJlRll5U2tWVWJHaG9UVlZ3VlZadGNFSmxSbGw1VTJ0V1ZXSkhhRzlVVmxaM1ZsWmFkR05GU214U2JHdzFWVEowVjFaW
   5 ZOcmFHaFNlbXhXVm0xNFlVMHhXbk5YYlVaclVqQTFSMVV5TVRSVk1rcElaSHBHVjFaRmIzZFdha1poVjBaT2NtRkhhRk5sYlhoWFZ
   6 MUdVMkpWYkRaWGExcHJZVWRGZUdOSE9WZGhhMHBvVmtSS1QyUkdTbkpoUjJoVFlYcFdlbGRYZUc5aU1XUkhWMjVTVGxOSGFGQlZiV
   7 djSE5WYlRGVFRWWlZlV042UmxoU2EzQmFWVmMxYjFZeFdYcGhTRXBWWVRKU1NGVnFSbUZYVm5CSVlVWk9WMVpHV2xkV2JHTjRUa2R
   8 YUZwaE1YQXpWRlphY21ReFpIUmtSMmhPWVROQ1NWZFhkRk5VTVZsM1RWaEdWMkV6YUdGWlZFWjNWRVp3Umxkc1pHdFdNSEJJV1ZWa
   9 V4V1JsWmhXVmROZUdFemNHaFNiVkpQVm14a00wMUdaRlZSYkdScVRWWnNOVlV5ZEd0aGJFNUdVMnhvVlZaV2NHaFdSVnBoWXpGa2R
  10 aDNWbGQ0YjFFd05WZFhiazVXWVRBMWIxUldXbGRPUm1SeVZtMTBhRlpyTlVkWk1GcHpWMjFLV1ZSWWFGZFdWbkJZV2tWVmVGWXhVb
  11 lhelF3Vm0xNFlWbFhUWGhqUldSVllYcFdUMVpzWXpWT1ZscHhVbTFHVjAxWGVGaFdSelZUVmpKS1NHRkdVbHBXUlZvelZsWmFZV1J
  12 Y21GSGNHeGlSbkIyVm0weE1HTXdOWE5pUmxwWVlsUnNXVlZ0ZUhkbGJGbDVUbFYwVjJKVldubFdNalZMVm1zeFIyTkdRbHBsYTFwe
  13 pGWVZXNXdXR0V4V25wV1Z6RkxVMGRHUjJKR1pHbFhSMmQ2VjFSS05GbFhUbGRUYmxKVFlsaFNWRlJXVm5kVFZscHlXa2h3VGxac2J
  14 TldWa3AwVW14a1RsWnJjRmxXYWtsNFRVWlZkMDFXV2s5V1JWcFlWV3BPYjJOc2JGZFhiSEJzWWxWYVNGbHJXbXRoUjBWM1kwWnNWM
  15 9WbXRzTkZrd1ZtRlpWa3AwVld4c1ZtRnJjSFphUjNoaFZsWkdkR1JHV2s1V01VcEpWMWQwYjFReFdYbFRibEpXWWtaYVYxbHNhRzl
  16 VjBaV2RFMVVVbXhXYlhoWFZtMXpOVlpWTVhKalJXaGFUVWRvZGxadGMzaFhSMFpKVjJ4a1YxSlZXVEJYVkVvMFlUSlNXRk5yWkZka
  17 tWYU1sZHNXbUZaVjA1WFVtNVNhMUpzY0U5V2JGSlhVMVphVlZOVVJsWk5hMVkwVlRKNFYxWXlTbFZpUmxwWFlsUkdkbFZyV2xabFY
  18 RkdUbWxTYTNCVlZrWmFWMlF4V1hoWGJrcFlZbFZhV0ZsWWNFZFdNVkpYVm0xMFdGSXdjSHBWTWpWTFZtMUdjazVXVWxwaGExcDZXV
  19 NXbFpYYUROV2FrcExVMFpXY2xwSFJsZGlTRUpaVjFod1MxSXhTWGxVYTJocFVtMW9WRlJYTVc5VU1WcHhVbXhPVTAxWGVGbFdWbWh
  20 VmxaclRrWlZlVk5zYkdoU2VteFlXV3hvYjJOc1dsVlNhemxUVFZkU01WWkhlRzloVmxwWFkwaG9WMUp0VWpaVVZscExZekZhYzJGS
  21 FFeFduUlRiR3hvVW0xb1dGVnVjRWRVUmxaMFRWVTVVMDFyY0VoWGEyUnZWRzFHTmxKVVFsZGlXR2hVVlhwR1NtVldVbGxoUmxacFl
  22 Sm9XVlpyVmt0aFJteHhVbTEwYTFKck5YbFpWV1J2VlRKS1JtTkdiRmhXYlZGM1YxWmFZVkl4WkZsYVIwWlRZWHBXVlZaR1pIcE5Wa
  23 JiRmROVm5CWVYxWmtSbVZHV2xsYVJUVlVVakpvVmxkV1pEQmtNV1JIWWtoT1ZtRXdOVkJWYlhoYVRXeFZlV042Vm1oaGVrWllWVEp
  24 V1RCV2JYaGhZVEExU0ZWWWFGaFhSMmhWV1cxek1XTldWblJOVnpsWVZteHdNRlJXV2s5V1ZrcHpWMjVvVm1KVVJYZFdNRnBoWkZaR
  25 xOV1dFSk1WbXBLTUZZeFduSk5WbVJZVjBkNFZWbHRkSGRXVm14VlZHdE9XRkpzU2xoWGExcExZVEF4V0ZWc2FGaGhNVnBvV1d0YVN
  26 WlRZekpHU0dKR1pGZGlSM1F6Vm0weGQxTXlVWGhWV0doWVYwZFNUMVpzWkZOalZsWjBUVmM1V2xadVFsbGFSV1JIWVcxS1NWRnJhR
  27 xSemxZWWtac05sWlhjRTlXVjBwWllVUk9WMkpZYUhKWk1qRlBVMGRXUjFwSGJGTlhSVVY0Vm0weGQxTnRWa1pPVldSWFYwZDRWVmx
  28 VkZkSVFsaFpWRVpMVkVaVmVVMVdaRk5OYXpWSFZqSXhSMVV3TVhWaFJsWllWak5TYUZwRVJtRldNWEJIWVVkNFUyVnRlRmhXUm1SN
  29 JSdlZHMUtSbU5IUmxkTlYxRjNXVlJCTVZOR1RsbGhSbVJwWWtWd1VGWnROWGRqTWs1SFZXeGtXR0V6VWxsVmJURTBWakZhZEdONlZ
  30 SmpSWGhXWVd0YWNsa3hXa2RqTVZwMFlrWk9UbFpXYkRaV2FrWmhXVlpzVjFSdVVsWlhSM2hXV1ZSR2QySXhWblJsU0dSVlRWZDRNR
  31 pWMnhvYVZkR1NsbFdiVEV3V1ZkV2MxcElTbUZTZW14V1dXeFdWMDVHYTNkV2JrNVhUVlp3UjFZeU5XRlpWa3BHVjIxb1lWSldjRkJ
  32 WlVab1YwMVhhSHBaVkVaTFpFWldjMXBHVmxkaVJuQlpWa2QwWVZkdFZsaFdhMmhUWWtaYWNGVnROVU5PYkdSVlVXMDVVMDFXY0RCV
  33 Fad1YySklRWGRXUmxwVFVUSkdSazFWVmxOaE1taGhXVlJHZDJOc1duUmxSM1JVVWpCYVNGbHJXbXRVYkVsNFVsaGtXRll6UWtoV2F
  34 WlhhRVJXUmxwaFpFVXhWVkZzY0ZkaVdHaFpWbXBHYjJFeFVuTlhiR2hXWWtkb1dGUlZaRk5XUmxwRlVteHdhMDFXY0RGWGExcGhWV
  35 9TRk5yWkZWaVIyaFVWbXhvUTFSV1duUk5XR1JUVFZaV05GVnNhRzlYUm1SSVpVWldWMDFIVVRCV2JGcHpWbFpPYzFSc1pGZGlSM2Q
  36 Vm14V1lVVjBXbFpyY0ZoWk1GWTBWMjFXY21ORmFGWmhhMW96VlRCa1MxSXhWbk5VYkdSWFRURkdObFp0TUhkbFJUVkhZa1pvVTFkS
  37 xkV1ZsWk9WbGw0VjJ0b2JGSnVRbGhXYWs1RFVrWndSVkp0ZEZkTmF6VklWako0YjJGWFJqWldiR3hZVmpOb1dGcEVSazlTTVZwWll
  38 ZDBVMVF4V2xkWGJrNXFVakpvWVZacVRtOVZSbFY0VjJ0a2FrMXJXa2hXYlhocllrZEtSMkl6YkZkaVZFVjNWMVphYzFkR1ZuSlhhe
  39 hSbGRUYmxKclRUTkNXRmxYZEhOT1JsSldWMnh3YTAxRVJsaFpWVnBoWVZkS2NsTnRhRmRTYkZweVZsZHplRkl4WkhWU2JGSm9UVEZ
  40 VG05aFJsWnhVbTVrVTFac1ducFdWM014VmpBeFZtSjZTbGRoYTI5M1YxWmtTbVZXU2xsaFJsSllVakZLV2xkWGVGZFpWbVJIWWtoT
  41 ZsaFIyaFVVakZLVmxaR1dtRlNNRFZIVmxoc2JGSXpVbGRVVjNSM1pXeFZlV1ZHVGxoaVZWWTFWbGQ0VTFZd01VZGpTSEJoVWxkU1Z
  42 cHpWbXBTVmsxWGFIWldiR1JMWTJzMVdHRkdXazVTYkc5NlYxWldZVll5VG5OYVNFcHJVbTFTVDFadGRIZFhWbHB4VTFSR2FFMVdjR
  43 tSMVpKV2tkd2FWSnNiM2RYYkZaclVqSkdjMU51VGxoaGEwcFdXV3RhWVZSR2JGVlJXR2hYVFdzMVNsa3dXbTloUlRGV1kwWldWMkp
  44 TUZaSGRHRlpWa3B6WTBVNVdsWXpVbWhVVjNoaFpFVXhTV0ZHVWs1V1ZGWkpWbTB3TVZZeFpFaFRhMnhTWVhwc1lWbHNVa2RrYkZKM
  45 FKNVZteFNWMkZHV25KalJFWldWak5DVkZacVNrdFdWa3BWVVd4d1YxSldjRmhYYTFKQ1pVWk9XRk5yYUdoU2F6VnpXV3hvYjFsV1d
  46 ZE5WbkF3VlRKNGMxWnRSbkpPVmxwWFlrWndNMVJVUm1Ga1IxWkpXa1pTVjJKRmNEWldha3A2VFZkR1JrMUlaRlJXUlZwWVdXdGFTM
  47 RWMFphY2xacmRHaFNiWFExVkZaYVMySkdTblJWYm5CWFlsaG9jbGxXV2twbFYwWkpXa1prYVZkSGFHOVdha3A2WlVaSmVHTkZaRmR
  48 VmtWVmQxWnNVa2RYYlZaSFZXNU9ZVkp0YUhCWldIQlhZakZhV0dSSFJsUk5hMncwVmxkNGExZEhTa2hWYkVKV1lsaG9lbFJzV2xOa
  49 VaYWNscEhSbE5XYmtKU1ZtMHdlRlV4WkZkaVJteHFVbTFTV1ZWdE1UUk5SbkJHVm1wQ1YxSXdjRWhaTUZKRFYyc3hSMWRZWkZkU1J
  50 UldXazlYUmtwMFpVaHdWMkpVVm5KWmEyUkxVMGRTUlZSc1pFNWhhMFY0Vm1wQ2ExTXhTWGxUYTFaWVlrZFNXRlJVUWt0VlZscDBZM
  51 9UMkZHU25WUmJrSldZV3R3ZGxSWGVHRmpiRnAwVW14b2FWWnJXVEJXTW5SdlV6SkdjMU5ZY0doU2JFcGhWakJvUTFkR1VuUmxSM1J
  52 Um14VlRWWktVRll3V21Gak1VNXlZVVpvVjJKSVFtOVhWRXA2WlVaWmVHTkZhRk5pUlRWUFZGVldkMVpzV1hoWGJFNVNUV3hHTlZWd
  53 xkRlNrbFdiR040WXpKR1YxTnVWbEppUmxwWVZGWmFkMVpHVmpaVGEzQnNVbTVDU0ZkcldtOWhWMFY2VVd4c1dGWnNTbEJXVkVwS1p
  54 SkdTRTlXWkdsV1dFSlhWbTB3TVZNeFdYaFhhMXBxVWxkb1ZsbHNhRzloUm13MlUydDBWRkpyY0hwWGExcHJZVmRGZDJKNlJsZGhhM
  55 llR3RXUjBWNVpVWm9XbFl6VWpKVVZWcHpZMVpPY21SR1RrNVdWRlkwVm1wSmVHTXhWWGxXYmxKc1VtMVNXRmxzVWtaTlJtUlhXa1p
  56 U2tkVGJuQlhWbnBHZWxaVVFYaFdiVW8yVTJ4a2FWWkZTWHBYYkZaV1pVWkplRmRzYkdGU1ZGWllXV3hrYjFkR1pGaE5SRVpTVFZkU
  57 1GWFIwNDJWbXhrVG1FelFrbFhWRUp2WXpGc1YxTnJXbGhpVjJoaFZGWmFkMVZHYTNoWGEyUnJVakJ3UjFSc1dtdGhSVEZZWkVST1Y
  58 WnJUV3R3U1ZWc2FHOWhiRXAwWlVac1YwMUhhRVJWTUZwM1VsWktjbU5IZUZkaE0wSTFWakowWVZZeVJsZFhXSEJvVW01Q1dGWnFUa
  59 dNR1JUV1Zad1dHUkZXbXhTYkhCNFZXMHhNR0Z0U2xaWGEyeGhVbFp3VkZaVVJtRlNNV1J4VTJ4a1RsWXhSak5XYlhCTFZXMVJkMDF
  60 ZUZkV1JuTmFSbWhYVFRGS2IxWlljRXRVTVVsNFYyNVdWbUY2YkZoV2JGSlhWbXhrV0dSSGRGWk5iRnA2VmpJMVUxUnNXa1pUYkZwY
  61 hSVFZteHdNRlZ0ZUd0V01rcHlVMnhhVjJKWVFreFVhMXB6VmpGT2RWTnJPVmRpU0VKWVYxZDBZVmxYVGtkWFdHUmhVbnBzY0ZSV1p
  62 ZFVWM1IzVjBaVmVXTkdUbGROVm5CSFdXNXdRMVl5Um5KWGJVWmhWbFp3Y2xwR1dtRmpNVTUwWVVkc1ZGSlZjR2hXYlRCNFRVWlplR
  63 pWbXBHZDFZeGNFZGFSbEpUVmtkNFdsZFdWbUZoTWtaWFZHdGFWR0pJUWxoVVZscExVa1prVjFkc2NHeFNia0pIVjJ0YWIyRkhTa2x
  64 Vm10a05HVldXa2RYYlhSV1RXeGFXRlpYZUd0V01rcFZZa2M1Vm1KWVRYaFZNbmhYVjBkV1NFOVdaRmRpUnpoNVZtMHhORkV4V2xoU
  65 dwR2EyTXlSa2RqUm1ST1RXMW9kbFp0Y0VOWlZsVjRXa1ZhVDFadFVsWlpiR1J2Vmtac2NtRkZUbE5OVm5CV1ZUSndRMkZGTVZkalJ
  66 TkdiSEpYYm1SWFRWWndNVlZYZUVkWFJscHpWMjVLVjJGcmNFOWFWVnAzVTFaT2RHUkdUbWxXYTNBelZtMXdRMkV5U1hsV2JHUllZV
  67 NTMVpXV205aE1WbDVVMnRvVlZkSGFGbFdiWGgzWTJ4cmVXTXphRmhXYkhBd1dWVmFVMVpHU2xaalJuQlhZVEZ3V0ZsVVJsWmxSbkJ
  68 VkZWM1YydFdWazFXVlhoVGJHUnFVbTVDV0ZsWGRIWmtNV3hWVW10d2JGSnNjRnBaYTFwVFlWWkplV0ZJV2xkV1JVcHlWbFJHYTFZe
  69 ZSc1pFNWhNMEpYVm0weE1GVXhXWGxTYmtwWVlsVmFhRlp0ZUZabFJsbDNXa1pPVkZJd1draFhhMlJ2VkdzeFJtRXpiRmRoYTFwVVZ
  70 eG9WbUp1UWtkVVZWcHJWakZ3Ums5V1pFNVdhM0EyVm0weE5GUXlSbGRUYmxaU1lrVktXVlp0ZUV0VlJsWlZVbXM1VjAxWFVucFdiW
  71 dOREJXUmxaaFUyMVJkMDFWYkdoU2JXaHdXVlJPUTFkc1pGaGxSbVJhVm14c05GWlhlR3RYUjBwSVZXeENWMkpZYUdoVVZWcDNWbXh
  72 VmxoU01taFlWMWN4TUdReFZrZFhibEpPVm1zMWNWVnRlR0ZOUmxKWFZXdE9WV0Y2UmxoWk1GSkRXVlphVjJOR1FsZFdSVVkwV1RJe
  73 5KV1ZFRjRWMGRTUlZSc2NGZFdNVXBKVm0xd1FtVkhUbk5YYmtaV1lraENUMVZxUmt0VFZsbDRWMjFHVkUxVmNIcFhhMmhIVmxkS1I
  74 aGhXVlJHWVUweFVuTlhiWFJZVWpGS1NWcEZaSGRVYkZwelYxUkdWMVpGYnpCWlZFWmhVMFpPY2xkc1VtbFNNMmhaVjFjd01WRXhTW
  75 lSbkJYV2xWYVlXTXlUa1phUjBaVFlsWktVRlpVUWxkVE1VNVhWMWhvVm1Fd05WaFVWM1JYVGtaWmVVNVZkRlZpUm5Bd1ZsZDRWMWR
  76 ZUZSc1pGZGliRXBRVm14b1UxWnNVbGRYYms1T1RWWnNOVnBWWkVkV01ERnlZMFZvV2sxR1NsQldiRnBoVW14a2RXTkdaR2xYUjJoN
  77 xaMFRsVk9WMDFXY0ZaVk1uQkRWR3hLYzJKRVRsVldiSEJvVmtSR1lWSnNaSE5oUmxaWFpXeGFNbGRyWkRSWlYwNVhWRzVLYTFKck5
  78 ZGtNVXBYVW01T2FsSnRVazlWYlRWRFUyeGFkR1ZIY0U1V2JGWTFWVEowYTFaSFNraGxSbVJhWVRKU2RsWXdXbk5qTWtaSFZHMW9VM
  79 9VbnBzV1ZWcVFuZGxWbGw1WlVoT1dHSlZWalJXYkdodlYyc3hSMk5HYUZwbGExcFlXWHBHZDFOSFZrZGFSMnhVVWxWd2FGWnRkR0Z
  80 VmtkS1NHRkdhRmRoYXpWMlZsVmFZV05XU25Ka1JtUlhZVE5CZUZkWGRHRldNVmw1VTJ0YWFsSnNXbGhaYkdoRFZFWldObEp0UmxkT
  81 xob2FGWkhlR0ZrVmtaelkwWmtWMDB5YURKWFdIQkxVekZKZUZWdVNsaGlSMmh3VldwR1MyRkdaRmhrUjBaVVRWVTFTRll5TlV0WFI
  82 TnNWbE5XUlVwWVZGVmFkMVpHV1hkYVJUbFRZa1UxZVZSc1dtdGhWbVJJWVVac1YySllRa3RhVlZwS1pWWktkVlZzVW1sU2JrSlJWb
  83 9WRkpzV25oV01uaFBZVlpKZUZOc2JGZFNiRXBNV1dwQmVHTXhjRWRoUjNCVFZqRktkbFpHV2xaTlZrNUhWMnRvVDFaVWJHOVZiWFJ
  84 YlhoTFpXeFplV042Vm1oU2JIQXdWbGQwYzFkc1dsZGpTRnBYWVd0d1RGVnFSazlqYlZaSVVteGtUazFFVVhkV2JYQkRXVlpSZVZSd
  85 ZOSFZraFBWbkJYWWtkM01GWnFTVEZVTWtaelUxaHNhRkl5YUZkWmEyUlRWa1paZDFkc1dtdE5XRUpJVmtkNFQxUnNXWGhUYWxaWFV
  86 QldOVlZ0ZUd0V1JtUklZVVpXV21KVVJsUldNRnB6WXpKR1JsUnNWbE5pV0dnMFZsY3hOR0V5Um5KTlZtaFdZV3RhV0ZadWNFWk5Sb
  87 VaRmhTYlhoWldrVmtSMVpXU25OWGFrSlZWbXhWTVZaVVNrdFdiR1J5WWtaYWFWZEhhRkZXYlhCTFV6Sk9jMVJ1VGxSaVIxSlBWbTE
  88 VW5CV01GWkxWVlphYzFWcmRGTk5WV3cwV1RCV2ExbFdTblJoU0VKWFlrWndNMXBWV21GU01XUjBaRVphVGxKRldsbFdiVEF4VlRKS
  89 xaaGExcFBXbFphVjJOc2NFZGFSMnhUVFRKb00xWnNZM2hPUm14WVUxaG9WbUpIYUU5V2JuQnpWakZzY2xkdVpFNVNiRXBYV1ZWak5
  90 SlhaREZrUjFkdVNsZGlWVnB4Vm0weE5HVldXWGxPVjNSVllrVndNVlZYZUd0WFIwVjRWMjVLV2xac2NFdGFSRXBQVW0xR1IyTkZOV
  91 dia3BvVW0xU2NGWnJXbUZXVmxwelZtMUdXbFl3TVRWV1IzUnpWVzFLU0ZWck9WWmhhMXBNVkZaYWEyTXhjRVZWYkhCWFlUSjNNRlp
  92 VmsxcmNGcFpWVnB2VmpKR2NtRXphRnBXUlhCSVZXcEdUMk14V25OVWJXeFVVbFZ3V1ZadE1IZGxSMGwzVFVob1dHSnJXbFJaVkU1V
  93 ZwM1kyeGFjMWRyWkdwTlYxSXdXbFZhVDJGV1NYcFpNMmhYWWtkUk1GbHFTa3BsUm1SeVlVWk9XRk5GU25aV1Z6QjRZakZaZUdKSVV
  94 VlNiRkpvWVRCd2RsWkdaSHBsUlRWWFZtNVNiRkl6VWxoVmFrSjNVMVp3Vmxkck9WaGlWVlkwVmpKd1QxWXdNVWRqU0hCYVpXdGFXR
  95 JVbXhvVjFKdGFIWlhWbHBQVW1zMVYySkdjR2hOYkVwVlZtcENZV014WkVoV2ExcHJVbTVDV0ZsdGRFdFhiR1J5Vm0xMFUwMVdjSHB
  96 VDFkd1RsWnNiM2RXUmxwcVRsWmtSMWR1VG1wU1JVcG9WbXhhV21ReFduSlhhM1JyVm10YWVWWXllR0ZVYlVwelUyNXNWMkpHU2tOY
  97 d4b1YySlVWa1JhVmxwaFkyeHdTV05IZUZOaVNFRjNWbXRrTUdNeFpFaFRhMmhXWW10S1YxbFhkSGRrVm5CWVpVZEdXRll3TlVkWGE
  98 SldjR2hYYkZaaFZESk9jMXBJVW1wU2F6VlpWVzEwZDJSc1duUk5TR2hQVWpGR05GWXlkR3RoYkVwWVZXeHNXbUV4VlhoWk1uaFhZM
  99 tTVlJzV21oTlJGWlJWbGN4TkdReFduTldXR3hyVWpOU1YxUlZVa2RYUm10M1ZXdGtWMkpWY0ZwWlZWcHZWMnhhVjFacVVsWmlSbkJ
User Language Tested N Time Output
Anders Kaseorg Rust \$\frac{10^{23500000}-1}9\$ 59.471s x
Neil JavaScript (Node.js) \$\frac{10^{90000}-1}9\$ 56.409s x
\$\endgroup\$
2
  • 4
    \$\begingroup\$ "No multithread allowed" is probably an unobservable requirement but you can probably replace it with "Your program will only be permitted to use a single processor core". \$\endgroup\$
    – Neil
    Feb 11, 2023 at 11:43
  • \$\begingroup\$ Current runenv ulimit -v 4194304; timeout 65 time <prog> \$\endgroup\$
    – l4m2
    Feb 11, 2023 at 12:42

2 Answers 2

10
\$\begingroup\$

Rust, \$3^{38\,000\,000}\$ in ~1 minute

How it works

Given position \$n\$, we convert \$3n\$ into a base-\$\frac43\$ representation with digits \$0, 1, 2, 3\$ using a relatively fast divide-and-conquer algorithm. Iterating through these base-\$\frac43\$ digits from most to least significant gives the shifts needed to maintain a three-character sliding window of the Base64 fixed point.

For example, given position \$27\$, we compute

$$3 · 27 = (3210201101)_{\frac43},$$

so we can jump the sliding window to the following positions (in units of \$\frac13\$ of a 6-bit character).

$$0 · \frac43 + 3 = 3, \quad 3 · \frac43 + 2 = 6, \quad 6 · \frac43 + 1 = 9, \quad 9 · \frac43 + 0 = 12, \\ 12 · \frac43 + 2 = 18, \quad 18 · \frac43 + 0 = 24, \quad 24 · \frac43 + 1 = 33, \quad 33 · \frac43 + 1 = 45, \\ 45 · \frac43 + 0 = 60, \quad 60 · \frac43 + 1 = 81.$$

Usage

Accepts a base-ten integer on STDIN, and outputs a character to STDOUT.

$ cargo build --release
$ python3 -c 'import gmpy2; print(gmpy2.mpz(3) ** 38000000)' > /tmp/in
$ time target/release/base64 < /tmp/in
1

real    1m0.092s
user    1m0.023s
sys     0m0.068s

Code

Cargo.toml

[package]
name = "base64"
version = "0.1.0"
edition = "2021"

[dependencies]
rug = "1.19.0"

src/main.rs

use rug::Integer;
use std::io::BufRead;

const ALPHABET: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

fn encode_low(n: Integer, k: u32) -> (Integer, Integer, Integer) {
    if k == 1 {
        let t = n * 3;
        let l = Integer::from(&t & 3);
        (3.into(), t >> 2, l)
    } else {
        let k0 = k / 2;
        let (p0, h0, l0) = encode_low(&n & !((!Integer::ZERO) << (k0 * 2)), k0);
        let k1 = k - k0;
        let (p1, h1, l1) = encode_low((n >> (k0 * 2)) * &p0 + h0, k1);
        (p1 * p0, h1, l1 << (k0 * 2) | l0)
    }
}

fn encode(n: Integer) -> Integer {
    if n == 0 {
        Integer::ZERO
    } else {
        let k = (n.significant_bits() + 1) / 2;
        let (_, h, l) = encode_low(n, k);
        encode(h) << (k * 2) | l
    }
}

fn char_at(n: Integer) -> char {
    let e = encode(n);
    let mut a: u32 = 0x566d30;
    for i in (0..e.significant_bits()).step_by(2).rev() {
        let k = 6 - e.get_bit(i + 1) as u32 * 4 - e.get_bit(i) as u32 * 2;
        a = (ALPHABET[((a >> (k + 12)) & 0x3f) as usize] as u32) << 16
            | (ALPHABET[((a >> (k + 6)) & 0x3f) as usize] as u32) << 8
            | (ALPHABET[((a >> k) & 0x3f) as usize] as u32);
    }
    char::from((a >> 16) as u8)
}

fn main() {
    for line in std::io::stdin().lock().lines() {
        let n: Integer = line.unwrap().parse().unwrap();
        println!("{}", char_at(n));
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ error: no override and no default toolchain set How to fix? \$\endgroup\$
    – l4m2
    Feb 11, 2023 at 12:28
  • 2
    \$\begingroup\$ @l4m2 It sounds like you uninstalled Rust but still have rustup. Try rustup update; rustup default stable. \$\endgroup\$ Feb 11, 2023 at 12:31
  • \$\begingroup\$ 62.3s on print("1"*25000000). I decide to test easy-generated indices first \$\endgroup\$
    – l4m2
    Feb 11, 2023 at 13:04
  • \$\begingroup\$ Which part is converting base? \$\endgroup\$
    – l4m2
    Feb 12, 2023 at 0:14
4
\$\begingroup\$

JavaScript (Node.js), 218 bytes

var btoa = s => Buffer.from(s).toString('base64');
var fp = (n, m = n + 1n) => m > 9n ? btoa(fp(n / 4n * 3n, (m + 3n) / 4n * 3n)).slice(Number(n % 4n), Number(n % 4n + m - n)) : "Vm0wd2QyU".slice(Number(n), Number(m));

Try it online! Link includes test cases. Using Node because it has a reasonably convenient btoa builtin, so it won't win any speed records but at least it scores reasonably well in time complexity.

Since the above code is recursive and stack space is expensive, here's an iterative version, although this only returns one character at a time so there's only one test case: Try it online!

var btoa = s => Buffer.from(s).toString('base64');
function fp(n) {
	stack = [];
	while (n) {
		stack.push(Number(n % 4n));
		n = n / 4n * 3n;
	}
	s = "Vm0wd2QyU";
	while (stack.length) s = btoa(s).substr(stack.pop(), 9);
	return s[0];
}
console.log(fp(3n ** 100000n));
\$\endgroup\$
7
  • \$\begingroup\$ Do console.log(fp(3n ** 100000n));. Crashes in 10s claiming lack of memory(2GB). Is it wrong version leading to memory limit? \$\endgroup\$
    – l4m2
    Feb 11, 2023 at 11:48
  • \$\begingroup\$ @l4m2 I wrote it recursively so for me it will go up to 3n ** 1965n but crashes with stack overflow for 3n ** 1966n. \$\endgroup\$
    – Neil
    Feb 11, 2023 at 11:53
  • \$\begingroup\$ I expanded stack so 3n**10000n still work \$\endgroup\$
    – l4m2
    Feb 11, 2023 at 11:59
  • \$\begingroup\$ @l4m2 I added an iterative conversion which was able to handle 3n ** 100000n. \$\endgroup\$
    – Neil
    Feb 11, 2023 at 12:20
  • \$\begingroup\$ 15.88s for 3**100000 \$\endgroup\$
    – l4m2
    Feb 11, 2023 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.